Submission #544406

#TimeUsernameProblemLanguageResultExecution timeMemory
5444061BeeNY1Cigle (COI21_cigle)C++17
100 / 100
234 ms67404 KiB
#include <bits/stdc++.h> using namespace std; int n,v[5005],dp[5005][5005],ma[5005]; int ans=0; int main() { cin>>n; for(int i=1; i<=n; i++) cin>>v[i]; for(int pas=1; pas<n; pas++) { int urca=pas+1,coboara=pas,nr=0; long long au=v[urca],du=v[coboara]; for(int i=1; i<=pas; i++) ma[i]=max(ma[i-1],dp[pas][i-1]); dp[urca][pas]=ma[pas]; while( urca<=n&&coboara>=1 ) { if(urca==n&&coboara==1) break; if(urca==n) coboara--; else if(coboara==1) { urca++; dp[urca][pas]=dp[urca-1][pas]; } else { if(au==du) urca++,coboara--,au+=v[urca],du+=v[coboara],nr++,dp[urca][pas]=max(dp[urca-1][pas],nr+ma[coboara]); else if(au<du) urca++,au+=v[urca],dp[urca][pas]=dp[urca-1][pas]; else coboara--,du+=v[coboara]; } } ans=max(ans,dp[n][pas]); } cout<<ans; return 0; }
#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...