# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
287938 | 2020-09-01T07:05:32 Z | dvdg6566 | Bigger segments (IZhO19_segments) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pi; typedef vector<ll> vi; typedef vector<pi> vpi; typedef long double ld; #define pb emplace_back #define mp make_pair #define f first #define s second #define SZ(x) (ll)x.size() #define ALL(x) x.begin(),x.end() #define lb lower_bound #define ub upper_bound const ll MAXN=200001; const ll MOD=1e9+7; const ll INF = 3e9; ll A[MAXN]; ll N; ll dp[MAXN]; ll S[MAXN]; int main(){ cin>>N; for(int i=1;i<=N;++i){ cin>>A[i]; A[i]+=A[i-1]; } dp[0]=0; S[0]=0; for(int i=1;i<=N;++i){ for(int j=0;j<i;++j){ if(A[i] >= S[j]){ if(dp[j]+1 >= dp[i]){ dp[i]=dp[j]+1; S[i] = x+A[i]-A[j]; } } } } cout<<dp[N]; }