Submission #168603

#TimeUsernameProblemLanguageResultExecution timeMemory
168603adletBigger segments (IZhO19_segments)C++17
37 / 100
1559 ms3408 KiB
// Example program #include <iostream> #include <string> using namespace std; const int N = 5e5 + 5; typedef long long ll; int n, ans, a[N]; pair < ll, int > dp[N]; ll pref[N]; int main() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; dp[i] = {pref[i], 1}; } for (int i = 2; i <= n; ++i) { for (int j = 1; j < i; ++j) { if (pref[i] - pref[j] >= dp[j].first) { if (dp[j].second + 1 > dp[i].second) dp[i] = {pref[i] - pref[j], dp[j].second + 1}; else if (dp[j].second + 1 == dp[i].second && pref[i] - pref[j] < dp[i].first) { dp[i].first = pref[i] - pref[j]; } } } } cout << dp[n].second; }
#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...