Submission #690938

#	Time	Username	Problem	Language	Result	Execution time	Memory
690938		demetrekokhreidze	Bigger segments (IZhO19_segments)	C++14	100 / 100	65 ms	20804 KiB

segments

#include <bits/stdc++.h>

#define ll long long 
#define pb push_back
#define f first
#define s second

using namespace std;

ll pref[500001], dp_cost[500001], dp_cnt[500001], l, r, dq[500001];

int main() {

    std::ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
  
    ll n;
    cin >> n;
  
    for (int i = 1; i <= n; ++i) {
        cin >> pref[i];
      	pref[i] += pref[i - 1];
        while (r - l && pref[i] - pref[dq[l + 1]] >= dp_cost[dq[l + 1]])
            l++;
        dp_cnt[i] = dp_cnt[dq[l]] + 1;
        dp_cost[i] = pref[i] - pref[dq[l]];
        while (dp_cost[dq[r]] - dp_cost[i] >= pref[i] - pref[dq[r]])
            r--;
        dq[++r] = 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