Submission #1198439

#TimeUsernameProblemLanguageResultExecution timeMemory
1198439aykhnBigger segments (IZhO19_segments)C++20
0 / 100
0 ms584 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3F3F3F3F3F3F3F3F const int MXN = 3e3 + 5; const int mod = 1e9 + 7; int dp[MXN][MXN]; void _() { int n; cin >> n; int a[n + 1], p[n + 1]; for (int i = 1; i <= n; i++) cin >> a[i]; p[0] = 0; for (int i = 1; i <= n; i++) p[i] = (i ? p[i - 1] : 0) + a[i]; auto sum = [&](int l, int r) { if (l > r) return 0LL; return p[r] - (l ? p[l - 1] : 0LL); }; for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) dp[i][j] = inf; dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { for (int k = 1; k <= i; k++) { if (dp[k - 1][j - 1] <= sum(k, i)) dp[i][j] = min(dp[i][j], sum(k, i)); } if (dp[i][j] < inf && j > 2) { assert(dp[i][j] - dp[i][j - 1] >= dp[i][j - 1] - dp[i][j - 2]); } } } for (int i = n; i >= 1; i--) { if (dp[n][i] < inf) { cout << i << '\n'; return; } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) _(); }
#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...