Submission #1326754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326754		simplemind_31	Feast (NOI19_feast)	C++20	12 / 100	92 ms	9112 KiB

feast

#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
/*ll n,k;
vector<ll> nums;
pair<ll,ll> solve(ll penal){
    pair<ll,ll> dp[n][2];
    dp[0][0]={0,0};
    dp[0][1]={nums[0]-penal,1};
    for(ll i=1;i<n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        pair<ll,ll> op1={dp[i-1][0].first+nums[i]-penal,dp[i-1][0].second+1};
        pair<ll,ll> op2={dp[i-1][1].first+nums[i],dp[i-1][1].second};
        dp[i][1]=max(op1,op2);
    }
    return max(dp[n-1][0],dp[n-1][1]);
}
ll main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    nums.resize(n);
    for(ll i=0;i<n;i++){
        cin >> nums[i];
    }
    ll l=0,r=1e18;
    while(l<r){
        ll mid=(l+r+1)>>1;
        // mayor mid=menor k
        if(solve(mid).second>=k){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    pair<ll,ll> res=solve(l);
    cout << res.first+k*l;
}*/
// sol 2
bool xd;
ll n,k,a,de[300002],iz[300002];
ll findne(ll x){return (x==de[x])?x:de[x]=findne(de[x]);}
ll findan(ll x){return (x==iz[x])?x:iz[x]=findan(iz[x]);}
struct link{
    ll val;
    link* left;
    link* right;
};
ll res=0;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    vector<ll> nums;
    for(ll i=0;i<n;i++){
        cin >> a;
        if(a>0)xd=true;
        if(!xd && a<=0)continue;
        if(!nums.empty() && a*nums.back()>0)nums.back()+=a;
        else nums.push_back(a);
    }
    while(!nums.empty() && nums.back()<=0)nums.pop_back();
    ll can=(nums.size()+1)/2;
    reverse(ALL(nums));
    nums.push_back(0);
    reverse(ALL(nums));
    nums.push_back(0);
    //for(auto u:nums)cout << u << ' ';
    cout << endl;
    priority_queue<pair<pair<ll,bool>,ll>,vector<pair<pair<ll,bool>,ll>>,greater<pair<pair<ll,bool>,ll>>> orden;
    for(ll i=1;i<nums.size()-1;i++){
        orden.push({{abs(nums[i]),(nums[i]>=0)},i});
    }
    for(ll i=0;i<nums.size();i++){
        de[i]=iz[i]=i;
    }
    while(can>k){
        ll top=orden.top().second;
        orden.pop();
        // unir con al lado
        //cout << "a";
        if(findne(top)!=top)continue;
        ll sig=findne(top+1),ante=findan(top-1);
        if(sig!=nums.size()-1 && ante!=0){can--;}
        else if(nums[top]>0){can--;}
        //cout << can << ' ' << top << ' ' << ante << ' ' << sig << '\n';
        //break;
        if(sig!=nums.size()-1){
            //unir;
            nums[top]+=nums[sig];
            de[sig]=sig+1;
            iz[sig]=sig-1;
        }
        if(ante!=0){
            nums[top]+=nums[ante];
            de[ante]=ante+1;
            iz[ante]=ante-1;
        }
        orden.push({{abs(nums[top]),(nums[top]>=0)},top});
        /*for(ll i=1;i<nums.size()-1;i++){
            if(findne(i)==i)cout << nums[i] << ' ';
        }
        cout << '\n';*/
        //break;
        // 1 2 3 4 5
        // 1 -2 3 -1 5
        // -1 3 -1 5
        // 
    }
    for(ll i=1;i<nums.size()-1;i++){
        if(findne(i)==i && nums[i]>0)res+=nums[i];
    }
    cout << res;
}

• 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