Submission #1022480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022480		phoenix	Bigger segments (IZhO19_segments)	C++17	100 / 100	113 ms	19120 KiB

segments

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 500500;

int n;
int a[N];
ll s[N];

int dp[N];
ll opt[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) 
        s[i] = s[i - 1] + a[i];
    
    vector<int> st;
    st.push_back(0);

    for (int i = 1; i <= n; i++) {
        int l = 0, r = (int)st.size();
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (s[i] >= opt[st[m]] + s[st[m]]) 
                l = m;
            else 
                r = m;
        }
        dp[i] = dp[st[l]] + 1;
        opt[i] = s[i] - s[st[l]];
        while (!st.empty() && opt[st.back()] + s[st.back()] >= opt[i] + s[i]) 
            st.pop_back();
        st.push_back(i);
    }
    cout << dp[n];
}

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