Submission #2874949
Source Code Expand
#include <algorithm> #include <cmath> #include <cstring> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> const int MOD = 1e9 + 7; const int iINF = 2147483647; const long long int llINF = 9223372036854775807; using namespace std; using ll = long long int; using P = pair<int, int>; using edge = struct { int to; int cost; }; #define REP(i, n) for (ll i = 0; i < (n); i++) #define FOR(i, n, m) for (ll i = (n); i < (m); i++) #define ALL(a) (a).begin(), (a).end() #define MAX(vec) *std::max_element(vec.begin(), vec.end()) #define MIN(vec) *std::min_element(vec.begin(), vec.end()) #define MAXI(vec) \ std::distance(vec.begin(), *std::max_element(vec.begin(), vec.end())) #define MINI(vec) \ std::distance(vec.begin(), *std::min_element(vec.begin(), vec.end())) int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; template <typename T, typename U> U READ(ll V, T a, U b) { REP(i, V) { cin >> a; b.push_back(a); } return b; } int main() { ll N = 0; vector<ll> A; vector<unsigned long long int> B; unsigned long long int sum = 0; ll po = 0; cin >> N; REP(i, N) { cin >> po; A.push_back(po); sum += po; B.push_back(sum); } ll mi = llINF; FOR(i, 1, N - 1) { ll left = B[i]; ll right = B[N - 1] - B[i]; ll lh = left / 2, rh = right / 2; ll l1 = lower_bound(B.begin(), B.begin(), lh) - B.begin(); ll l2 = lower_bound(B.begin(), B.end(), left + rh) - B.begin(); ll w[2] = {0, -1}; REP(k, 4) { vector<ll> pa(4); pa[0] = B[l1 + w[k % 2]]; pa[1] = B[i] - B[l1 + w[k % 2]]; pa[2] = B[l2 + w[k / 2]] - B[i]; pa[3] = B[N - 1] - B[l2 + w[k / 2]]; if (MIN(pa) == 0) { continue; } mi = min(mi, MAX(pa) - MIN(pa)); } } cout << mi << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Equal Cut |
User | grayf |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2085 Byte |
Status | WA |
Exec Time | 112 ms |
Memory | 3564 KB |
Judge Result
Set Name | Sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 600 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | WA | 1 ms | 256 KB |
sample_03.txt | WA | 1 ms | 256 KB |
subtask_1_01.txt | AC | 1 ms | 256 KB |
subtask_1_02.txt | WA | 110 ms | 3564 KB |
subtask_1_03.txt | WA | 42 ms | 2036 KB |
subtask_1_04.txt | WA | 76 ms | 2412 KB |
subtask_1_05.txt | WA | 1 ms | 256 KB |
subtask_1_06.txt | AC | 12 ms | 892 KB |
subtask_1_07.txt | WA | 57 ms | 2284 KB |
subtask_1_08.txt | AC | 32 ms | 2036 KB |
subtask_1_09.txt | WA | 55 ms | 2156 KB |
subtask_1_10.txt | AC | 68 ms | 3564 KB |
subtask_1_11.txt | WA | 92 ms | 3564 KB |
subtask_1_12.txt | AC | 40 ms | 2036 KB |
subtask_1_13.txt | WA | 60 ms | 2412 KB |
subtask_1_14.txt | AC | 19 ms | 1276 KB |
subtask_1_15.txt | WA | 12 ms | 768 KB |
subtask_1_16.txt | WA | 39 ms | 2036 KB |
subtask_1_17.txt | WA | 34 ms | 2036 KB |
subtask_1_18.txt | WA | 3 ms | 384 KB |
subtask_1_19.txt | AC | 69 ms | 3564 KB |
subtask_1_20.txt | WA | 112 ms | 3564 KB |
subtask_1_21.txt | WA | 48 ms | 2036 KB |
subtask_1_22.txt | WA | 38 ms | 1396 KB |
subtask_1_23.txt | WA | 79 ms | 3564 KB |
subtask_1_24.txt | AC | 91 ms | 3564 KB |
subtask_1_25.txt | AC | 90 ms | 3564 KB |
subtask_1_26.txt | AC | 89 ms | 3564 KB |
subtask_1_27.txt | AC | 91 ms | 3564 KB |
subtask_1_28.txt | WA | 92 ms | 3564 KB |
subtask_1_29.txt | WA | 91 ms | 3564 KB |
subtask_1_30.txt | WA | 90 ms | 3564 KB |
subtask_1_31.txt | WA | 90 ms | 3564 KB |
subtask_1_32.txt | WA | 91 ms | 3564 KB |
subtask_1_33.txt | WA | 89 ms | 3564 KB |
subtask_1_34.txt | WA | 75 ms | 3564 KB |
subtask_1_35.txt | WA | 74 ms | 3564 KB |
subtask_1_36.txt | WA | 71 ms | 3564 KB |
subtask_1_37.txt | WA | 74 ms | 3564 KB |