Submission #730698

#	Time	Username	Problem	Language	Result	Execution time	Memory
730698		bgnbvnbv	Feast (NOI19_feast)	C++14	100 / 100	368 ms	25584 KiB

feast

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,k,pre[maxN],R[maxN],val[maxN],a[maxN];
set<pli>ms1,ms2;
set<ll> ms3;
set<ll>::iterator it;
void solve()
{
    cin >> n >> k;
    //k=1;
    for(int i=1;i<=n;i++) cin >> a[i],pre[i]=pre[i-1]+a[i];
    ll last=-1;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=0) continue;
        ll j=i;
        ll sum=0;
        while(j<=n&&a[j]>0)
        {
            sum+=a[j];
            j++;
        }
        R[i]=j-1;
        val[i]=sum;
        ms1.insert({sum,i});
        ms3.insert(i);
        if(last!=-1)
        {
            ms2.insert({-(pre[i-1]-pre[R[last]]),i});
        }
        last=i;
        ans+=sum;
        i=j-1;
    }
    //cout << ans << '\n';
    while(ms3.size()>k)
    {
        if(ms2.begin()->fi<=ms1.begin()->fi)
        {
            ll x=ms2.begin()->fi;
            ans-=ms2.begin()->fi;
            ll id=ms2.begin()->se;
            ms2.erase(ms2.begin());
            it=ms3.lower_bound(id);
            ms1.erase({val[id],id});
            it--;
            ms1.erase({val[*it],*it});
            val[*it]+=val[id]-x;
            R[*it]=R[id];
            ms1.insert({val[*it],*it});
            it++;
            ms3.erase(it);
        }
        else
        {
            ans-=ms1.begin()->fi;
            ll id=ms1.begin()->se;
            ll l=-1,r=-1;
            it=ms3.upper_bound(id);
            if(it!=ms3.end()) r=*it;
            it--;
            if(it!=ms3.begin())
            {
                it--;
                l=*it;
            }
            ms1.erase(ms1.begin());
            ms3.erase(id);
            if(l!=-1)
            {
                ms2.erase({-(pre[id-1]-pre[R[l]]),id});
            }
            if(r!=-1)
            {
                ms2.erase({-(pre[r-1]-pre[R[id]]),r});
            }
            if(l!=-1&&r!=-1)
            {
                ms2.insert({-(pre[r-1]-pre[R[l]]),r});
            }
        }
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

feast.cpp: In function 'void solve()':
feast.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   47 |     while(ms3.size()>k)
      |           ~~~~~~~~~~^~

• 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