Submission #1192858

#TimeUsernameProblemLanguageResultExecution timeMemory
1192858lopkusBigger segments (IZhO19_segments)C++20
37 / 100
1595 ms3284 KiB
#include <bits/stdc++.h> 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<int> dp(n + 1, 0); std::vector<int64_t> e(n + 1, 0); dp[1] = 1; e[1] = a[1]; for(int i = 2; i <= n; i++) { for(int j = i - 1; j >= 0; j--) { if(pref[i] >= pref[j] + e[j]) { if(dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; e[i] = pref[i] - pref[j]; } else if(dp[i] == dp[j] + 1) { e[i] = std::min(e[i], pref[i] - pref[j]); } } } } std::cout << dp[n]; } 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...