Submission #1192883

#TimeUsernameProblemLanguageResultExecution timeMemory
1192883lopkusBigger segments (IZhO19_segments)C++20
13 / 100
0 ms328 KiB
#include <bits/stdc++.h> #define int64_t int void solve() { int n; std::cin >> n; std::vector<int64_t> a(n + 1); for(int i = 1; i <= n; i++) { std::cin >> a[i]; } std::vector<int64_t> pref(n + 1); for(int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + a[i]; } std::vector<std::pair<int,int>> dp(n + 1, {- 1, - 1}); dp[0] = {0, 0}; for(int i = 1; i <= n; i++) { std::pair<int,int> opt = {- 1, - 1}; for(int j = i - 1; j >= 0; j--) { if(pref[i] >= pref[j] + dp[j].second) { dp[i] = std::max(dp[i], {dp[j].first + 1, pref[j]}); opt = std::max({opt, {dp[j].first + 1, pref[j]}}); } } if(opt.first == - 1 || opt.first < dp[i - 1].first) { dp[i].first = dp[i - 1].first; dp[i].second = dp[i - 1].second + a[i]; } else { dp[i] = {opt.first, pref[i] - opt.second}; } } std::cout << dp[n].first; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t = 1; //std::cin >> t; while (t--) { solve(); } 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...