Submission #560098

#TimeUsernameProblemLanguageResultExecution timeMemory
560098Yazan_AlattarCigle (COI21_cigle)C++14
0 / 100
3 ms2772 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define F first #define S second #define pb push_back #define endl "\n" #define all(x) x.begin(), x.end() const int M = 5007; const ll inf = 1e18; const ll mod = 1e9 + 7; const double pi = acos(-1); const double eps = 1e-6; const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0}; const int block = 320; int n, a[M], dp[M][M], ans; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int i = 1; i <= n; ++i){ int lenk = 0, lenj = 0, k = i, cnt = 0; // cout << i << " "; for(int j = i; j <= n; ++j){ lenj += a[j]; while(k && lenk < lenj){ lenk += a[--k]; dp[i][j] = max(dp[i][j], dp[k][i - 1] + cnt); } if(k) dp[i][j] = max(dp[i][j], dp[k][i - 1] + cnt); if(lenj == lenk) ++cnt; // cout << i << " " << j << " " << k << " " << cnt << " " << dp[i][j] << endl; // cout << dp[i][j] << " "; } for(int j = i + 1; j <= n; ++j) dp[i][j] = max(dp[i][j], dp[i][j - 1]); // cout << endl; } for(int i = 1; i <= n; ++i) ans = max(ans, dp[i][n]); cout << ans << endl; 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...