Submission #842693

#	Time	Username	Problem	Language	Result	Execution time	Memory
842693		vjudge1	Bigger segments (IZhO19_segments)	C++17	100 / 100	68 ms	16096 KiB

segments

#include <iostream>
using namespace std;
long long int a[500005], c[500005], d[500005], res[500005];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[i] = c[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        d[i] = max(d[i], d[i - 1]);
        res[i] = res[d[i]] + 1;
        int h = lower_bound(c + 1, c + n + 1, c[i] * 2 - c[d[i]]) - c;
        if (h <= n) d[h] = i;
    }
    cout << res[n];
}

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