Submission #1358600

#TimeUsernameProblemLanguageResultExecution timeMemory
1358600nobasistakenBigger segments (IZhO19_segments)C++20
37 / 100
1593 ms3396 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define endl '\n'
#define all(v) v.begin(),v.end()
bool testcases=0;
void solve(){
	int n;
	cin>>n;
	int v[n+1];
	int pref[n+1];
	memset(pref,0,sizeof(pref));
	for(int i=1;i<=n;i++){
		cin>>v[i];
		pref[i]+=pref[i-1]+v[i];
	}
	int ans[n+1];
	int ls[n+1];
	memset(ls,0,sizeof(ls));
	memset(ans,0,sizeof(ans));
	for(int i=1;i<=n;i++){
		for(int j=i;j>0;j--){
			if(ls[j-1]<=pref[i]-pref[j-1]){
				ls[i]=pref[i]-pref[j-1];
				ans[i]=ans[j-1]+1;
				break;
			}
		}
	}
	cout<<ans[n]<<endl;
}
signed main() {
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    if (testcases)cin>>t;
    for(int i=1;i<=t;i++){
        solve();
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...