Submission #560423

#TimeUsernameProblemLanguageResultExecution timeMemory
560423Yazan_AlattarCigle (COI21_cigle)C++14
13 / 100
3 ms2844 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){ for(int j = 1; j < i; ++j){ if(i > 1) dp[j][i - 1] = max(dp[j][i - 1], dp[j][i - 2]); dp[j][i - 1] = max(dp[j][i - 1], dp[j - 1][i - 1]); } int lenk = 0, lenj = 0, k = i - 1, cnt = 0; for(int j = i; j <= n; ++j){ lenj += a[j]; while(k > 1 && lenk < lenj) lenk += a[k--]; if(lenj == lenk) ++cnt; dp[i][j + 1] = max(dp[i][j + 1], dp[k][i - 1] + cnt); } } 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...