제출 #1158925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158925		Hanksburger	Feast (NOI19_feast)	C++20	100 / 100	136 ms	15548 KiB

feast

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define int long long
int a[300005], l[300005], r[300005];
set<pair<int, int> > s;
vector<int> vec;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, sz, sum=0, cnt=0, ans=0;
    cin >> n >> k;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
        if ((a[i-1]>0)^(a[i]>0))
        {
            vec.push_back(sum);
            sum=0;
        }
        sum+=a[i];
    }
    vec.push_back(sum);
    if (vec[0]<=0)
        vec.erase(vec.begin());
    if (vec.size() && vec.back()<=0)
        vec.erase(--vec.end());
    sz=vec.size();
    for (int i=0; i<sz; i++)
    {
        s.insert({abs(vec[i]), i});
        l[i]=(i==0)?-1:(i-1);
        r[i]=(i==sz-1)?-1:(i+1);
        if (vec[i]>0)
            cnt++;
    }
    //for (int x:vec)
    //        cout << x << ' ';
    //    cout << '\n';
    while (cnt>k)
    {
        int ind=(*s.begin()).second, val=vec[ind], ok=1;
        if (l[ind]==-1 || r[ind]==-1)
            ok=0;
        //cout << "ind " << ind << '\n';
        s.erase({abs(vec[ind]), ind});
        if (vec[ind]>0)
            cnt--;
        if (l[ind]!=-1)
        {
            if (vec[l[ind]]>0)
                cnt--;
            s.erase({abs(vec[l[ind]]), l[ind]});
            val+=vec[l[ind]];
            vec[l[ind]]=0;
            l[ind]=l[l[ind]];
            if (l[ind]!=-1)
                r[l[ind]]=ind;
        }
        if (r[ind]!=-1)
        {
            if (vec[r[ind]]>0)
                cnt--;
            s.erase({abs(vec[r[ind]]), r[ind]});
            val+=vec[r[ind]];
            vec[r[ind]]=0;
            r[ind]=r[r[ind]];
            if (r[ind]!=-1)
                l[r[ind]]=ind;
        }
        if (ok)
        {
            s.insert({abs(val), ind});
            vec[ind]=val;
            if (val>0)
                cnt++;
        }
        else
        {
            int L=l[ind], R=r[ind];
            if (L!=-1)
                r[L]=R;
            if (R!=-1)
                l[R]=L;
            vec[ind]=0;
        }
        //for (int x:vec)
        //    cout << x << ' ';
        //cout << '\n';
        
    }
    for (int i=0; i<sz; i++)
        ans+=vec[i]*(vec[i]>0);
    cout << ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29