Submission #467437

#TimeUsernameProblemLanguageResultExecution timeMemory
467437julian33Cigle (COI21_cigle)C++14
48 / 100
1089 ms10424 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=5e3+5; //make sure this is right const int mod=1e9+7; int dp[mxN][mxN],a[mxN]; int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ int pre=i-j; int k=i-j+1; int p=pre; int s1=0; int s2=0; dp[i][j]=dp[pre][1]; int cnt=0; while(p && k<i){ if(s1+a[p]<=s2+a[k]){ s1+=a[p--]; } else{ s2+=a[k++]; } if(s1==s2){ cnt++; maxa(dp[i][j],cnt+dp[pre][pre-p+1]); } } deb(i,j,dp[i][j],cnt); } for(int j=i-1;j>=1;j--) maxa(dp[i][j],dp[i][j+1]); } cout<<dp[n][1]<<"\n"; }
#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...