Submission #308807

#	Time	Username	Problem	Language	Result	Execution time	Memory
308807		nikatamliani	Bigger segments (IZhO19_segments)	C++14	100 / 100	449 ms	17024 KiB

segments

#include <bits/stdc++.h>
#define f first
#define s second 
#define ll long long 
using namespace std;
const int N = 5e5 + 10;
pair < int, ll > dp[N];
ll sum[N], p[N], n;
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> sum[i], sum[i] += sum[i - 1];
    for(int i = 0; i <= n; ++i) {
        if(i && dp[i].f == dp[i - 1].f) {
            dp[i].s = min(dp[i].s, dp[i - 1].s + sum[i] - sum[i - 1]);
        }
        if(i && dp[i].f < dp[i - 1].f) {
            dp[i].f = dp[i - 1].f;
            dp[i].s = dp[i - 1].s + sum[i] - sum[i - 1];
        }
        int l = i + 1, r = n, ans = -1;
        while(r >= l) {
            int m = l + r >> 1;
            if(sum[m] - sum[i] >= dp[i].s) {
                r = m - 1;
                ans = m;
            } else {
                l = m + 1;
            }
        }
        if(~ans && dp[ans].f == dp[i].f + 1) {
            dp[ans].s = min(dp[ans].s, sum[ans] - sum[i]);
        }
        if(~ans && dp[ans].f < dp[i].f + 1) {
            dp[ans].f = dp[i].f + 1;
            dp[ans].s = sum[ans] - sum[i];
        }
    }
    cout << dp[n].f << '\n';
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:22:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             int m = l + r >> 1;
      |                     ~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27