Submission #1198445

#TimeUsernameProblemLanguageResultExecution timeMemory
1198445aykhnBigger segments (IZhO19_segments)C++20
37 / 100
95 ms2196 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; array<int, 2> dp[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); }; dp[0] = {0, 0}; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { if (dp[j - 1][1] <= sum(j, i) && dp[j - 1][0] + 1 >= dp[i][0]) dp[i] = {dp[j - 1][0] + 1, sum(j, i)}; } } cout << dp[n][0] << '\n'; } 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...