Submission #332450

#	Time	Username	Problem	Language	Result	Execution time	Memory
332450		dolphingarlic	Bigger segments (IZhO19_segments)	C++14	100 / 100	71 ms	12140 KiB

segments

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
typedef long long ll;
using namespace std;

ll pref[500001], dp_cost[500001];
int dp_cnt[500001], lptr = 0, rptr = 0, dq[500001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int a;
        cin >> a;
        pref[i] = pref[i - 1] + a;
        while (rptr - lptr && pref[i] - pref[dq[lptr + 1]] >= dp_cost[dq[lptr + 1]])
            ++lptr;
        dp_cnt[i] = dp_cnt[dq[lptr]] + 1;
        dp_cost[i] = pref[i] - pref[dq[lptr]];
        while (dp_cost[dq[rptr]] - dp_cost[i] >= pref[i] - pref[dq[rptr]])
            --rptr;
        dq[++rptr] = i;
    }
    cout << dp_cnt[n];
    return 0;
}

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