题目传送门

题意简述

存在变量 $x$ ，初始时 $x=0$ 。给定 $n$ 次操作按序进行，操作类型以下有两种：

• 1 y 表示将 $x$ 赋值为 $y$
• 2 y 表示将 $x$ 加上 $y$

你可以从中删除不超过 $k$ 个操作，使得最终的 $x$ 最大，输出最大值。

题目分析

首先可以发现，当一个赋值操作被保留时，对于这个赋值操作，它前面的操作都可以忽略，可以把它当做一个“新的开始”，删除它前面的操作是多余的。

这时我们可以考虑从后往前枚举操作，因为前面的操作不影响后面的操作，且后面的赋值和相加操作对结果的影响更大。

为了使结果尽可能大，我们可以贪心选取相加操作中对结果负贡献尽可能小的，正的直接计入和，负的用一个优先队列处理就行；而对于赋值操作，讨论删或不删的情况，取最大值即可，并且要保证在当前赋值操作后的赋值操作都被删除。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int n,k;
long long sum,ans=-0x3f3f3f3f3f3f3f;
int t[maxn],a[maxn];
priority_queue<int> q;

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>t[i]>>a[i];

    for(int i=n;i>=1;i--){
        if(t[i]==1){
            ans=max(ans,sum+a[i]);
            k--;
            if(k<0)break;
            while(q.size()>k){   //保证元素个数不超过k，超过k时则弹出队首
                sum+=q.top();
                q.pop();
            }
        }
        else{
            if(a[i]>=0)sum+=a[i];//正的直接加入
            else {
                q.push(a[i]);    //负的丢进优先队列
                while(q.size()>k){
                    sum+=q.top();
                    q.pop();
                }
            }
        }
    }
    ans=max(ans,sum);
    cout<<ans<<endl;
    return 0;
}