Submission #176026

#	Time	Username	Problem	Language	Result	Execution time	Memory
176026		istlemin	Bigger segments (IZhO19_segments)	C++14	100 / 100	442 ms	45368 KiB

segments

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

#define rep(i, a, b) for(ll i = a; i < ll(b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;

int main() {
    //cin.sync_with_stdio(0); cin.tie(0);
    //cin.exceptions(cin.failbit);
    ll n;
    cin>>n;
    vi a(n);
    rep(i,0,n) cin>>a[i];

    vi pSum(n+1);
    rep(i,0,n) pSum[i+1] = pSum[i]+a[i];

    vi dp(n,-1);

    dp[0] = 0; 

    multiset<tuple<ll,ll,ll>> pq;
    ll pqSub = 0;

    ll closestFound = 0;
    rep(i,1,n){
        pq.emplace((pSum[i]-pSum[closestFound]) + pqSub,i,closestFound);
        
        pqSub += a[i];
        
        while(pq.size()&&get<0>(*pq.begin())<=pqSub){
            ll dist,ind,closest;
            tie(dist,ind,closest) = *pq.begin();
            pq.erase(pq.begin());

            dp[ind] = dp[closest]+1;
        
            closestFound = max(closestFound,ind);
        }

        //rep(j,0,n) cout<<dp[j]<<" ";
        //cout<<endl;
    }
    

    ll ans = 0;
    rep(i,0,n) ans = max(ans,dp[i]);
    cout<<ans+1<<endl; 
}

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