제출 #1125010

#제출 시각아이디문제언어결과실행 시간메모리
1125010nikatamlianiBigger segments (IZhO19_segments)C++20
37 / 100
1594 ms2228 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...