Submission #1022475

#TimeUsernameProblemLanguageResultExecution timeMemory
1022475phoenixBigger segments (IZhO19_segments)C++17
37 / 100
7 ms552 KiB
#include<bits/stdc++.h> #ifdef LOCAL #include "../prettyprint.hpp" #define cerr cout #define debug(x) cerr << "\033[36m"<< __LINE__ << ":\033[39m " << (#x) << " = " << (x) << '\n' #else #define cerr if(false) cout #define debug(x) 42 #endif using namespace std; using ll = long long; const int N = 3030; int n; int a[N]; ll s[N]; int dp[N]; ll opt[N]; int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; dp[0] = 0; opt[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (s[i] >= opt[j] + s[j]) { dp[i] = max(dp[i], dp[j] + 1); opt[i] = s[i] - s[j]; } } } cout << dp[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...