Submission #707971

#TimeUsernameProblemLanguageResultExecution timeMemory
707971arcaneCigle (COI21_cigle)C++17
0 / 100
4 ms4180 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define mp make_pair #define pb emplace_back int32_t main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, ptr, cnt, ans = 0; cin >> n; int arr[n], dp[n][n], pref[n][n], prefs[n + 1]; for (int i = 0; i < n; i++) cin >> arr[i]; prefs[0] = 0; for (int i = 0; i < n; i++) prefs[i + 1] = prefs[i] + arr[i]; for (int i = 1; i < n; i++) fill(dp[i], dp[i] + n, 0); fill(dp[0], dp[0] + n, 1); for (int i = 1; i < n; i++){ ptr = i - 1; cnt = 0; for (int j = 0; j < n; j++){ if (!j) pref[i - 1][j] = dp[j][i - 1]; else pref[i - 1][j] = max(dp[j][i - 1], pref[i - 1][j - 1]); } for (int j = i; j < n; j++){ if (j == i) dp[i][j] = pref[i - 1][i - 1]; else{ dp[i][j] = dp[i][j - 1]; while (ptr >= 0 and prefs[i] - prefs[ptr + 1] <= prefs[j] - prefs[i]){ if (prefs[i] - prefs[ptr + 1] == prefs[j] - prefs[i]) cnt += 1; dp[i][j] = max(dp[i][j], dp[ptr][i - 1] + cnt); ptr--; } } } } for (int i = 0; i < n; i++) ans = max(ans, dp[i][n - 1]); cout << ans - 1 << '\n'; }
#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...