Submission #1157445

#TimeUsernameProblemLanguageResultExecution timeMemory
1157445raczekCigle (COI21_cigle)C++20
0 / 100
2 ms2376 KiB
#include<bits/stdc++.h> using namespace std; #ifdef DEBUG auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";} auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";} #define debug(X...) cerr<<"["#X"]: ", [](auto...$) {((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif #define int long long const int INF = 1e18+7; #define mp(x, y) make_pair(x, y) #define fi first #define se second #define eb emplace_back int32_t main() { cin.tie(0)->sync_with_stdio(0); int n; cin>>n; vector<int> a(n); for(auto& v : a) cin>>v; vector dp(n, vector(n, 0LL)); for(int l=0;l<n;l++) { int pref = 0, suf = a[l], bty = 0; if(l-1 >= 0) pref = a[l-1]; int x = l-1, y = l; int bst = 0; vector<int> prefMax; for(int i=0;i<l;i++) prefMax.eb(max(prefMax.size() ? prefMax.back() : 0, dp[i][l-1])); while(y < n && x >= 0) { dp[l][y] = prefMax[x]+bty; bst = max(bst, dp[l][y]); if(pref < suf) { x--; if(x >= 0) pref += a[x]; continue; } if(pref > suf) { y++; if(y < n) suf += a[y]; continue; } if(pref == suf) { dp[l][y] = prefMax[x]+bty; bst = max(bst, dp[l][y]); bty++; x--; if(x >= 0) pref += a[x]; continue; } } while(y < n) dp[l][y++] = bst; } int res = 0; for(int i=0;i<n;i++) res = max(res, dp[i][n-1]); cout<<res; }
#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...