Submission #384386

#	Time	Username	Problem	Language	Result	Execution time	Memory
384386		vanic	Bigger segments (IZhO19_segments)	C++14	13 / 100	2 ms	364 KiB

segments

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>

using namespace std;

typedef long long ll;
const int maxn=5e5+5;


ll a[maxn];
ll pref[maxn];
array < ll, 3 > dp[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i];
		pref[i+1]=pref[i]+a[i];
	}
	dp[0]={a[0], -1, 1};
	int pos=0;
	int pos1=-1;
	for(int i=1; i<n; i++){
		while(pos<i-1 && pref[i+1]-pref[pos+2]>=dp[pos+1][0]){
//			cout << "retard " << pref[i+1]-pref[pos+2] << endl;
			pos++;
		}
//		cout << pref[i+1]-pref[pos+1] << endl;
		if(pref[i+1]-pref[pos+1]>=dp[pos][0]){
			dp[i]={pref[i+1]-pref[pos+1], pos, dp[i-1][2]+1};
			pos1=pos;
			pos=i;
			continue;
		}
		while(pos1<i-1 && pref[i+1]-pref[pos1+2]>=dp[pos1+1][0]){
			pos1++;
		}
		dp[i]={pref[i+1]-pref[pos1+1], pos1, dp[i-1][2]};
	}
	cout << dp[n-1][2] << '\n';
	return 0;
}

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