Submission #1023969

#TimeUsernameProblemLanguageResultExecution timeMemory
1023969yellowtoadBigger segments (IZhO19_segments)C++17
37 / 100
1578 ms9560 KiB
#include <iostream> using namespace std; long long n, a[500010], sum, dp[500010], p[500010], cnt, pos; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { sum = a[i]; for (int j = i-1; j >= 0; j--) { if (dp[j] <= sum) { dp[i] = sum; p[i] = j; break; } sum += a[j]; } } pos = n; while (pos > 0) { pos = p[pos]; cnt++; } cout << cnt << endl; }
#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...