제출 #559903

#제출 시각아이디문제언어결과실행 시간메모리
559903Yazan_AlattarCigle (COI21_cigle)C++14
48 / 100
1088 ms8564 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 = i; j <= n; ++j){ int lenk = 0, lenj = 0, pos = i, cnt = 0; for(int k = i - 1; k; --k){ lenk += a[k]; while(pos < j && lenk > lenj) lenj += a[pos++]; dp[i][j] = max(dp[i][j], dp[k][i - 1] + cnt); if(lenj == lenk) ++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...