제출 #1127974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127974		heeheeheehaaw	Bigger segments (IZhO19_segments)	C++20	100 / 100	179 ms	19864 KiB

segments

#include <bits/stdc++.h>
#define int long long

using namespace std;

int v[500005];
pair<int, int> dp[500005];

signed main()
{
    int n;
    cin>>n;

    cin>>v[1];
    dp[1] = {v[1], 1};
    priority_queue<pair<int, int>> pq;
    pq.push({-v[1] - v[1], 1});
    int b = 0;
    for(int i = 2; i <= n; i++)
    {
        cin>>v[i];
        v[i] += v[i - 1];
        while(!pq.empty())
        {
            pair<int, int> a = pq.top();
            if(v[i] - v[a.second] < dp[a.second].first)
                break;
            pq.pop();
            b = max(b, a.second);
        }

        dp[i] = {v[i] - v[b], dp[b].second + 1};
        pq.push({-dp[i].first - v[i], i});
    }

    cout<<dp[n].second<<'\n';
    return 0;
}

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