Submission #1125010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125010		nikatamliani	Bigger segments (IZhO19_segments)	C++20	37 / 100	1594 ms	2228 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,mod=1e9+7;
int n,p[N],ans,l,r,md,x;
pair<int, int> dp[N];

void maxi(pair<int, int> &me, pair<int, int> he) {
	if (me.first > he.first) {
		return;
	}

	if (me.first < he.first) {
		me = he;
	} else {
		me.second = min(me.second, he.second);
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;

	for (int i=1; i<=n; i++) {
		cin>>p[i];
	}
	for (int i=1; i<=n; i++){
		p[i]+=p[i-1];
	}
	dp[0].second=1e18;
	for (int i=1; i<=n; i++){
		dp[i].first = 1;
		dp[i].second = p[i];
		for (int j=0; j<i; j++){
			if (dp[j].second<=p[i]-p[j]){
				maxi(dp[i],{dp[j].first+1,p[i]-p[j]});
			}
		}
	}
	cout<<dp[n].first;
}

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