Submission #905875

#TimeUsernameProblemLanguageResultExecution timeMemory
905875Blistering_BarnaclesCigle (COI21_cigle)C++17
100 / 100
126 ms171468 KiB
//Billions of bilious blue blistering barnacles in a thundering typhoon! //Yesterday is history, tomorrow is a mystery, today is a gift of God, which is why we call it the present. #include<bits/stdc++.h> #define F first #define S second #define lx node * 2 #define rx node * 2 + 1 #define md ((s + e) / 2) #define mid (l + (r - l) / 2) #define all(x) x.begin(), x.end() typedef long long ll; using namespace std; int a[5005], dp[5005][5005], Dp[5005][5005]; void solve(){ int n; cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } int ans = 0; for(int i = 1; i <= n; i++){ int sumL = 0, sumR = 0, cnt = 0; int k = i - 1; for(int j = i + 1; j <= n; j++){ dp[i][j] = dp[i][j - 1]; sumR += a[j - 1]; while(k > 1 && sumL < sumR){ sumL += a[k--]; } cnt += (sumL == sumR); dp[i][j] = max(dp[i][j], Dp[k][i - 1] + cnt); Dp[i][j] = max(Dp[i - 1][j], dp[i][j]); } ans = max(ans, dp[i][n]); } cout << ans << "\n"; } int main(){ ios::sync_with_stdio(0), cin.tie(0); int tt = 1; //cin >> tt; while(tt--){ solve(); } }
#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...