Submission #8959410
Source Code Expand
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define MOD 1000000007
#define MOD2 998244353
#define int long long
//#define PI 3.14159265358979
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
for (int i = 0; i < A.size(); i++)
os << A[i] << " ";
os << endl;
return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
int N = A.size();
int M;
if (N > 0)
M = A[0].size();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
os << A[i][j] << " ";
os << endl;
}
return os;
}
typedef pair< int, int > pii;
typedef long long ll;
struct edge {
int from, to, d, c;
edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
from = _from;
to = _to;
d = _d;
c = _c;
}
bool operator<(const edge &rhs) const {
return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
}
};
struct aabb {
int x1, y1, x2, y2;
aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};
typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
int to, cap, rev, cost;
flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;
const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);
template < typename T, typename U >
bool chmin(T &x, const U &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
struct initializer {
initializer() {
cout << fixed << setprecision(11);
}
};
initializer _____;
int N, M, K, T, Q;
signed main() {
cin >> N;
vector< int > A(N);
rep(i, N) cin >> A[i];
vector< int > S(N + 1, 0);
rep(i, N) S[i + 1] = S[i] + A[i];
int l = 1, r = 3;
int ans = LINF;
for (int m = 2; m < N - 1; m++) {
while (r <= m)
++r;
while (l < m - 1 && abs(S[m] - S[l] - S[l]) > abs(S[m] - S[l + 1] - S[l + 1])) {
++l;
}
while (r < N && abs(S[N] - S[r] - S[r] + S[m]) > abs(S[N] - S[r + 1] - S[r + 1] + S[m])) {
++r;
}
int MAX = max(max(S[l], S[m] - S[l]), max(S[r] - S[m], S[N] - S[r]));
int MIN = min(min(S[l], S[m] - S[l]), min(S[r] - S[m], S[N] - S[r]));
chmin(ans, MAX - MIN);
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Equal Cut |
User |
AltTTT |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
2915 Byte |
Status |
AC |
Exec Time |
77 ms |
Memory |
3328 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 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 |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
75 ms |
3072 KB |
subtask_1_03.txt |
AC |
27 ms |
1536 KB |
subtask_1_04.txt |
AC |
52 ms |
2176 KB |
subtask_1_05.txt |
AC |
1 ms |
256 KB |
subtask_1_06.txt |
AC |
7 ms |
640 KB |
subtask_1_07.txt |
AC |
35 ms |
2048 KB |
subtask_1_08.txt |
AC |
19 ms |
1408 KB |
subtask_1_09.txt |
AC |
34 ms |
1920 KB |
subtask_1_10.txt |
AC |
40 ms |
2688 KB |
subtask_1_11.txt |
AC |
53 ms |
3072 KB |
subtask_1_12.txt |
AC |
23 ms |
1664 KB |
subtask_1_13.txt |
AC |
37 ms |
2176 KB |
subtask_1_14.txt |
AC |
11 ms |
896 KB |
subtask_1_15.txt |
AC |
8 ms |
640 KB |
subtask_1_16.txt |
AC |
19 ms |
1920 KB |
subtask_1_17.txt |
AC |
17 ms |
1664 KB |
subtask_1_18.txt |
AC |
2 ms |
384 KB |
subtask_1_19.txt |
AC |
33 ms |
3072 KB |
subtask_1_20.txt |
AC |
77 ms |
3072 KB |
subtask_1_21.txt |
AC |
29 ms |
1792 KB |
subtask_1_22.txt |
AC |
26 ms |
1152 KB |
subtask_1_23.txt |
AC |
48 ms |
2816 KB |
subtask_1_24.txt |
AC |
52 ms |
3328 KB |
subtask_1_25.txt |
AC |
51 ms |
3328 KB |
subtask_1_26.txt |
AC |
51 ms |
3328 KB |
subtask_1_27.txt |
AC |
51 ms |
3328 KB |
subtask_1_28.txt |
AC |
51 ms |
3328 KB |
subtask_1_29.txt |
AC |
52 ms |
3328 KB |
subtask_1_30.txt |
AC |
51 ms |
3328 KB |
subtask_1_31.txt |
AC |
51 ms |
3328 KB |
subtask_1_32.txt |
AC |
51 ms |
3328 KB |
subtask_1_33.txt |
AC |
51 ms |
3328 KB |
subtask_1_34.txt |
AC |
36 ms |
3328 KB |
subtask_1_35.txt |
AC |
37 ms |
3328 KB |
subtask_1_36.txt |
AC |
35 ms |
3328 KB |
subtask_1_37.txt |
AC |
36 ms |
3328 KB |