This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, q, A[5005], memo[505][505], dp[5005][5005];
/*
int dp(int x, int y){
if(y >= n)return 0;
if(memo[x][y] != -1)return memo[x][y];
int ans = 0, cur = 0, in = y - 1, cnt = 0, tmp = 0;
for(int i = y; i <= n; i++){
cnt += A[i];
while(cur < cnt && in >= x)cur += A[in--];
ans = max(ans, tmp + dp(y, i + 1));
if(cur == cnt && in >= x)tmp++;
}
return memo[x][y] = ans;
}
*/
int S[5005];
void solve(){
cin >> n;
for(int i=1;i<=n;i++)cin >> A[i];
//memset(memo, -1, sizeof(memo));
/*
int ans = 0;
for(int i=2;i<=n;i++)ans = max(ans, dp(1, i));// cout << dp(1, i) << ' ';
cout << ans;
*/
for(int i=n;i>=1;i--){
int cur = 0, in = i - 1, cnt = 0, tmp = 0, mx = 0;
S[n + 1] = 0;
for(int j = n; j >= i; j --)S[j] = max(S[j+1], dp[i][j]);
for(int j = i; j <= n; j++){
cnt += A[j];
while(cur < cnt && in >= 1){
mx = max(mx, tmp + S[j+1]);
dp[in][i] = mx;
cur += A[in--];
}
if(cur == cnt)tmp++;
}
while(in >= 1)dp[--in][i] = max(mx, tmp);
}
cout << *max_element(dp[1], dp[1] + n + 1);
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message (stderr)
cigle.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
58 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |