Submission #1250734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250734		nasjes	Feast (NOI19_feast)	C++20	12 / 100	216 ms	21236 KiB

feast

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 2*(1e6)+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
//#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m, k;
ll t;
ll a[dim];
ll dp[dim];
int main() {

    ll  u, w,q,   v, y;
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    set<pll> sml;
    set<pll> s;
    ll sm=0;
    ll fl=1;
    ll c=0;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        if (fl && a[i] >= 0) {
            sm += a[i];
        } else if (fl == 0 && a[i] < 0) {
            sm += a[i];
        } else {
            c++;
            s.insert({c, sm});
            sm=0;
            fl = 1 - fl;
            sm += a[i];
        }
    }

    c++;
    s.insert({c, sm});
    while(s.size()>0 && (*s.begin()).se<=0){
        s.erase(s.begin());
    }

    while(s.size()>0 && (*s.rbegin()).se<=0){
        s.erase(*s.rbegin());
    }
    m=(s.size()+1)/2;
    ll ans=0;
    for(auto x: s){
        ll p1=x.fi;
        ll p2=x.se;
      //  cout<<p1<<" "<<p2<<endl;
        if(p2>0)ans+=x.se;
        sml.insert({abs(p2), p1});
    }
  //  cout<<ans<<endl;
    if(m<=k){
        cout<<ans<<endl;
        return 0;
    }
    else m-=k;
    while(m>0){
        m--;
       // cout<<m<<endl;
        while(s.size()>0 && (*s.begin()).se<=0){
            s.erase(s.begin());
            pll x=(*s.begin());
            ll p1=x.fi;
            ll p2=x.se;
            sml.erase({abs(p2), p1});
        }

        while(s.size()>0 && (*s.rbegin()).se<=0){
            s.erase(*s.rbegin());
            pll x=(*s.rbegin());
            ll p1=x.fi;
            ll p2=x.se;
            sml.erase({abs(p2), p1});
        }

        pll cur=(*sml.begin());
        sml.erase(cur);
        ans-=cur.fi;

        //cout<<cur.fi<<" "<<cur.se<<endl;
        ll cnt=0;
        auto it1=s.lower_bound({cur.se, -inf});
        cnt+=(*it1).se;
        if(it1==s.begin() || it1==(--s.end())){
            s.erase(it1);
            continue;
        }

        s.erase(it1);
        it1=s.lower_bound({cur.se, -inf});
        auto it2=s.lower_bound({cur.se+1, 0});

        if(it1!=s.begin()){
            it1--;
            pll p1=(*it1);
            s.erase(it1);
            cnt+=p1.se;
        //    cout<<" merge "<<p1.fi<<" "<<p1.se<<endl;
            sml.erase({abs(p1.se), p1.fi});
        }
        if(it2!=s.end()){
            pll p2=(*it2);
            s.erase(it2);
            cnt+=p2.se;
        //    cout<<" merge "<<p2.fi<<" "<<p2.se<<endl;
            sml.erase({abs(p2.se), p2.fi});
        }
        //cout<<cnt<<"--"<<endl;
        sml.insert({abs(cnt), cur.se});
        s.insert({cur.se, cnt});
    }
    cout<<ans<<endl;



    return 0;
}

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