Submission #1132278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132278		Agageldi	Bigger segments (IZhO19_segments)	C++17	0 / 100	134 ms	269672 KiB

segments

/*
ID: agageld1
LANG: C++17
TASK:
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 400005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
#define rep(c, a, b) for(c = a; c <= b; c++)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, t, a[N], sum[N];
string s, g, h;
deque <int> v[N];

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i= 1;i<=n;i++) {
		cin >> a[i];
	}
	v[1].pb(a[1]);
	sum[1] = a[1];
	int cnt = 1;
	for(int i = 2; i <= n; i++) {
		if(sum[cnt] < sum[cnt - 1]) {
			v[cnt].pb(a[i]);
			sum[cnt] += a[i];
		}
		else {
			cnt++;
			v[cnt].pb(i);
			sum[cnt] += a[i];
		}
		while(sum[cnt] >= sum[cnt-1]) {
			bool tr = 0;
			for(int j = cnt; j > 1; j--) {
				while(sum[j] - v[j][0] >= sum[j - 1] + v[j][0]) {
					sum[j-1] += v[j][0];
					sum[j] -= v[j][0];
					v[j-1].pb(v[j][0]);
					v[j].pop_front();
					tr = 1;
				}
			}
			if(!tr) break;
		}
	}
	if(sum[cnt] < sum[cnt - 1]) cnt--;
	cout << cnt << '\n';
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27