Submission #2773809


Source Code Expand

Copy
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define REREP(i,n) for(int i = int(n - 1); i >= 0; i--)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define REFOR(i, m, n) for(int i = int(n - 1);i >= int(m);i--)
#define ALL(obj) (obj).begin(),(obj).end()

#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VD vector<double>
#define VVD vector<vector<double>>
#define VVVD vector<vector<vector<double>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VVVL vector<vector<vector<ll>>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define VVVB vector<vector<vector<bool>>>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVVS vector<vector<vector<string>>>

#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<ll,ll>
#define VPII vector<pair<int,int>>
#define VVPII vector<vector<pair<int,int>>>
#define VVVPII vector<vector<vector<pair<int,int>>>>
#define VPLL vector<pair<ll,ll>>
#define VVPLL vector<vector<pair<ll,ll>>>
#define VVVPLL vector<vector<vector<pair<ll,ll>>>>

#define SUMI(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SUMD(obj) accumulate((obj).begin(), (obj).end(), 0.)
#define SUML(obj) accumulate((obj).begin(), (obj).end(), 0LL)
#define SORT(obj) sort((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) sort((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n

const ll HMOD = (ll)1e9 + 7;
const ll LMOD = 998244353;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;
const long double EPS = 1e-10;

//integer
class Integer {
public:
	ll gcd(ll a, ll b) {
		if (a == 0 || b == 0) return 0;
		if (a < b) swap(a, b);
		while (b != 0) {
			a = a%b;
			swap(a, b);
		}
		return a;
	}

	ll lcm(ll a, ll b) {
		if (a == 0 || b == 0) return 0;
		return a / gcd(a, b)*b;
	}

	set<ll> divisor(ll N){
		set<ll> st;
		for (ll i = 1; i*i <= N; i++) {
			if (N%i == 0) {
				st.insert(i);
				st.insert(N / i);
			}
		}
		return st;
	}

	//a vector that has prime factors of N (this includes only elements, which has no number of each prime factor)
	vector<ll> prime_factorization(ll N) {
		vector<ll> v;
		ll M = N;
		for (ll i = 2; i*i <= N; i++) {
			if (M%i == 0) v.push_back(i);
			while (M%i == 0) M /= i;
		}
		if (M != 1) v.push_back(M);
		return v;
	}

	int bitcount(ll N, int K){
		int cnt = 0;
		for (int i = 0; i < K; i++) if (N & (1 << i)) cnt++;
		return cnt;
	}

	ll digitsum(ll N, int K){
		ll sum = 0;
		for (; N > 0; N /= K) sum += N%K;
		return sum;
	}
};

//geometry
class Geometry {
public:	
	double dist(double x1, double y1, double x2, double y2) {
		return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
	}

	bool intersection_judgment(double ax, double ay, double bx, double by, double cx, double cy, double dx, double dy) {
		double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
		double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
		double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
		double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);
		return tc * td < 0 && ta * tb < 0;
	}

};

//eratosthenes
class Eratosthenes{
public:
	vector<bool> primary(int N) {
		vector<bool> primary(N + 1, true);
		primary[0] = false;
		if (N == 0) return primary;
		primary[1] = false;
		for (int i = 1; i*i <= N; i++) if (primary[i]) for (int j = 2 * i; j <= N; j += i) primary[j] = false;
		return primary;
	}
};

//combination mod
class Combination_Mod {
public:
	VL factorial;

	//N! table
	void set(ll N, ll quotient){
		factorial.resize(N + 1, 1);
		for (ll i = 1; i <= N; i++) {
			factorial[i] *= factorial[i - 1] * i;
			factorial[i] %= quotient;
		}
		return;
	}

	//repeat square method y = x^n mod quotient 
	ll rsm(ll x, ll n, ll quotient) {
		ll y = 1;
		while (n > 0) {
			if (n & 1) {
				y *= x;
				y %= quotient;
			}
			x *= x;
			x %= quotient;
			n >>= 1;
		}
		return y;
	}

	//modulus of nCk - combination mod 
	ll nCk(ll n, ll k, ll quotient) {
		if (n < k || n <= 0 || k <= 0) return 0;
		ll nCk = (factorial[n] % quotient);
		nCk *= rsm(factorial[k], quotient - 2, quotient);
		nCk %= quotient;
		nCk *= rsm(factorial[n - k], quotient - 2, quotient);
		return (nCk % quotient);
	}
};

//combination
class Combination{
public:
	VVL nCk;
	VVD nCkP;

	void set(int N){
		nCk.resize(N + 1);
		REP(i,N + 1) nCk[i].resize(N + 1,0);
		
		nCk[0][0] = 1;
		for (int n = 1; n <= N; n++) {
			for (int k = 0; k <= n; k++) {
				if(k == 0) nCk[n][k] = nCk[n - 1][k];
				else nCk[n][k] = nCk[n - 1][k - 1] + nCk[n - 1][k];

			}
		}
	}

	void setP(int N) {
		nCkP.resize(N + 1);
		REP(i, N + 1) nCkP[i].resize(N + 1, 0.);

		nCkP[0][0] = 1;
		for (int n = 1; n <= N; n++) {
			for (int k = 0; k <= n; k++) {
				if (k == 0) nCkP[n][k] = nCkP[n - 1][k]/2.;
				else nCkP[n][k] = (nCkP[n - 1][k - 1] + nCkP[n - 1][k])/2.;
			}
		}
	}

};

//union-find
class Union_Find {
public:
	VI node;
	void set(int n){
		node.resize(n);
		REP(i, n) node[i] = i;
	}

	int root(int n) {
		if (node[n] == n) return n;
		else return node[n] = root(node[n]);
	}

	void unite(int n, int m) {
		if (n > m) swap(n, m);
		n = root(n);
		m = root(m);
		if (n == m) return;
		else node[m] = n;
	}
};

//dijkstra
class Dijkstra{
public:
	VVPII edge;
	VVI dist;
	void set(int N, int inf){
		edge.resize(N);
		dist.resize(N);
		REP(i, N) dist[i].resize(N);
		REP(i, N)REP(j, N) dist[i][j] = inf;
	}

	void make_edge(int from, int to, int cost) {
		edge[from].push_back({ to,cost });
	}

	void dijkstra(int start) {
		priority_queue<PII, vector<PII>, greater<PII>> pq;
		dist[start][start] = 0;
		pq.push({ 0,start });
		while (!pq.empty()) {
			int from = pq.top().second;
			pq.pop();
			REP(i, edge[from].size()) {
				int to = edge[from][i].first;
				if (dist[start][to] > dist[start][from] + edge[from][i].second) {
					dist[start][to] = dist[start][from] + edge[from][i].second;
					pq.push({ dist[start][from] + edge[from][i].second,to });
				}
			}
		}
	}
};

//bellman ford
class Bellman_Ford {
public:
	struct edge{
		int from, to, cost;
	};
	int N;
	VI node;
	vector<edge> graph;

	void set(int node_, int inf) {
		N = node_;
		node.resize(node_);
	}

	void make_edge(int from,int to, int cost){
		graph.push_back({from,to,cost});
	}

	void bellman_ford(int start,int inf) {
		REP(i, N) node[i] = inf;
		node[start] = 0;		
		REP(i, N - 1) REP(j, graph.size()) if (node[graph[j].to] > node[graph[j].from] + graph[j].cost) node[graph[j].to] = node[graph[j].from] + graph[j].cost;
	}
};

//ford fulkerson
class Ford_Fulkerson{
public:
	struct edge {
		int to, cap, rev;
	};

	int node, start, goal;
	vector<vector<edge>> graph;
	vector<bool> visit;

	void set(int node_, int start_, int goal_) {
		node = node_;
		start = start_;
		goal = goal_;
		graph.resize(node);
		visit.resize(node);
	}

	void make_edge(int from, int to, int cap) {
		graph[from].push_back({ to,cap,(int)graph[to].size() });
		graph[to].push_back({ from,0,(int)graph[from].size() - 1 });
	}

	int dfs(int from, int flow) {
		if (from == goal) return flow;
		visit[from] = false;
		REP(i, graph[from].size()) {
			if (visit[graph[from][i].to] && (graph[from][i].cap > 0)) {
				int dflow = dfs(graph[from][i].to, min(flow, graph[from][i].cap));
				if (dflow > 0) {
					graph[from][i].cap -= dflow;
					graph[graph[from][i].to][graph[from][i].rev].cap += dflow;
					return dflow;
				}
			}
		}
		return 0;
	}

	int maxflow(void) {
		int maxflow = 0;
		while (1) {
			REP(i, graph.size()) visit[i] = true;
			int flow = dfs(start, 1);
			if (flow == 0) return maxflow;
			maxflow += flow;
		}
	}
};

//longest increasing subsequence
class Longest_Increasing_Subsequence{
public:
	int N;
	VI dp, ar;

	void set(int N_){
		N = N_;
		dp.resize(N, LINF);
		ar.resize(N);// ar has to be set value.
	}

	int make(void){
		REP(i, N) *lower_bound(ALL(dp), ar[i]) = ar[i];
		return distance(dp.begin(), lower_bound(ALL(dp), LINF));
	}

};

//least common ancestor
class Least_Common_Ancestor {
public:
	int node;
	int MAXLOG2;
	VVI edge;
	VI depth;
	VVI parent;

	void set(int node_, int MAXLOG2_) {
		node = node_;
		MAXLOG2 = MAXLOG2_;
		edge.resize(node);
		depth.resize(node);
		parent.resize(node);
		REP(i, node) parent[i].resize(MAXLOG2);
	}

	void dfs(int root, int root_from) {
		depth[root] = 0;
		parent[root][0] = root_from;
		stack<pair<int, int>> st;
		st.push({ root,root_from });

		while (!st.empty()) {
			int from = st.top().first;
			int from_from = st.top().second;
			st.pop();
			REP(i, edge[from].size()) {
				int to = edge[from][i];
				if (to != from_from) {
					depth[to] = depth[from] + 1;
					parent[to][0] = from;
					st.push({ to,from });
				}
			}
		}
		return;
	}

	//make table
	void initialize(int N) {
		REP(k, MAXLOG2 - 1) {
			REP(i, N) {
				if (parent[i][k] < 0) parent[i][k + 1] = -1;
				else parent[i][k + 1] = parent[parent[i][k]][k];
			}
		}
		return;
	}

	//get least common ancestor
	int get(int a, int b) {
		if (depth[a] > depth[b]) swap(a, b);
		REP(k, MAXLOG2 - 1) if (((depth[b] - depth[a]) >> k) & 1) b = parent[b][k];
		if (a == b) return a;
		REREP(k, MAXLOG2) {
			if (parent[a][k] != parent[b][k]) {
				a = parent[a][k];
				b = parent[b][k];
			}
		}
		return parent[a][0];
	}
};

//directed acyclic graph
class Directed_Acyclic_Graph{
public:

	int N;
	Dijkstra dijkstra;
	struct edge {
		int dest, cost;
		bool need;
	};
	vector<vector<edge>> output;
	VI input;
	VI topological_order;

	void set(int N_, int inf){
		N = N_;
		dijkstra.set(N, inf);
		output.resize(N);
		input.resize(N,0);
	}

	void make_edge(int from, int to, int cost){
		dijkstra.make_edge(from, to, cost);
		output[from].push_back({to, cost, true});
	}

	void make_dag(int start) {
		dijkstra.dijkstra(start);
		REP(i, N) {
			REP(j, output[i].size()) {
				int from = i;
				edge &e = output[i][j];
				if (dijkstra.dist[start][e.dest] - dijkstra.dist[start][from] != e.cost) e.need = false;
			}
		}
	}

	bool topological_sort(int start){
		REP(i, N) REP(j, output[i].size()) if (output[i][j].need) input[output[i][j].dest]++;

		stack<int> st;
		st.push(start);
		while(!st.empty()){
			int from = st.top();
			st.pop();
			topological_order.push_back(from);
			REP(i, output[from].size()) {
				edge &e = output[from][i];
				if (e.need) {
					input[e.dest]--;
					if (input[e.dest] == 0) st.push(e.dest);
				}
			}
		}
		
		bool valid = true;
		REP(i, N) if (input[i] > 0) valid = false;
		return valid;
	}	
};

//binary indexed tree
class Binary_Indexed_Tree {
public:
	int N;
	ll ini;
	vector<ll> bit;
	
	void set(int N_, ll ini_) {
		N = N_;
		ini = ini_;
		bit.resize(N + 1);
		for (int i = 0; i <= N; i++) bit[i] = ini;
	}

	//sum
	void add(int i, ll w) {
		for (int j = i; j <= N; j += j & -j) bit[j] += w;
	}

	ll sum(int i) {
		ll ret = ini;
		for (int j = i; j >= 1; j -= j & -j) ret += bit[j];
		return ret;
	}

	//max
	void inc(int i, ll w) {
		for (int j = i; j <= N; j += j & -j) bit[j] = (bit[j]>w)?bit[j]:w;
	}

	ll max(int i) {
		ll ret = ini;
		for (int j = i; j >= 1; j -= j & -j) ret = (ret>bit[j])?ret:bit[j];
		return ret;
	}

	//min
	void dec(int i, ll w) {
		for (int j = i; j <= N; j += j & -j) bit[j] = (bit[j]<w) ? bit[j] : w;
	}

	ll min(int i) {
		ll ret = ini;
		for (int j = i; j >= 1; j -= j & -j) ret = (ret<bit[j]) ? ret : bit[j];
		return ret;
	}


};

void YN(bool flag){
	cout << ((flag) ? "YES" : "NO") << endl;
}

void Yn(bool flag) {
	cout << ((flag) ? "Yes" : "No") << endl;
}

void yn(bool flag) {
	cout << ((flag) ? "yes" : "no") << endl;
}

int main() {
	ll N; cin >> N;
	VL A(N); REP(i, N) cin >> A[i];

	ll high = HINF, low = 0, center;

	ll ans = HINF;

	while(high > low + 1){
		center = (high + low) / 2;
		ll P = 0, Q = 0, R = 0, S = 0;
		int i = 0;

		for(;i<N - 3;++i){
			if(P + A[i] <= center) P += A[i];
			else break;
		}

		for (; i<N - 2; ++i) {
			if (Q + A[i] <= center) Q += A[i];
			else break;
		}

		for (; i<N - 1; ++i) {
			if (R + A[i] <= center) R += A[i];
			else break;
		}

		for (; i<N; ++i) {
			if (S + A[i] <= center) S += A[i];
			else break;
		}

		//cout << center << " " << P << " " << Q << " " << R << " " << S << endl;

		if(i == N){
			ans = min(ans, abs(max({ P,Q,R,S }) - min({ P,Q,R,S })));
			high = center;
		}
		else low = center;
	}
	cout << ans << endl;
	
	return 0;
}

Submission Info

Submission Time
Task D - Equal Cut
User ningenMe
Language C++14 (GCC 5.4.1)
Score 0
Code Size 13482 Byte
Status WA
Exec Time 84 ms
Memory 1792 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 15
WA × 28
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 82 ms 1664 KB
subtask_1_03.txt WA 29 ms 896 KB
subtask_1_04.txt AC 56 ms 1280 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt WA 8 ms 384 KB
subtask_1_07.txt AC 39 ms 1152 KB
subtask_1_08.txt WA 22 ms 768 KB
subtask_1_09.txt WA 37 ms 1152 KB
subtask_1_10.txt AC 45 ms 1408 KB
subtask_1_11.txt AC 59 ms 1664 KB
subtask_1_12.txt WA 28 ms 896 KB
subtask_1_13.txt AC 41 ms 1152 KB
subtask_1_14.txt WA 12 ms 512 KB
subtask_1_15.txt WA 9 ms 384 KB
subtask_1_16.txt WA 22 ms 1024 KB
subtask_1_17.txt WA 20 ms 896 KB
subtask_1_18.txt WA 2 ms 256 KB
subtask_1_19.txt WA 40 ms 1664 KB
subtask_1_20.txt WA 84 ms 1664 KB
subtask_1_21.txt WA 33 ms 1024 KB
subtask_1_22.txt AC 29 ms 768 KB
subtask_1_23.txt WA 54 ms 1536 KB
subtask_1_24.txt WA 56 ms 1792 KB
subtask_1_25.txt WA 57 ms 1792 KB
subtask_1_26.txt WA 56 ms 1792 KB
subtask_1_27.txt WA 59 ms 1792 KB
subtask_1_28.txt WA 59 ms 1792 KB
subtask_1_29.txt WA 56 ms 1792 KB
subtask_1_30.txt WA 58 ms 1792 KB
subtask_1_31.txt WA 57 ms 1792 KB
subtask_1_32.txt WA 63 ms 1792 KB
subtask_1_33.txt WA 57 ms 1792 KB
subtask_1_34.txt WA 41 ms 1792 KB
subtask_1_35.txt WA 42 ms 1792 KB
subtask_1_36.txt WA 44 ms 1792 KB
subtask_1_37.txt WA 41 ms 1792 KB