第3回ドワコン予選 D - ネタだけ食べたい寿司

• 問題

問題概要

{X_i},{Y_i} (0<=i<N, X_i > Y_i) と自然数Mが与えられる.
各i についてX_i,Y_i を選んでいく.
ただし,X_iを選べるのはM回までで,i<N-1でM回選んでしまうとそれ以降のY_iは得られない.
得られる合計を最大化せよ.
1 <= N,M <= 10⁵

解法

まず, M>=Nのケースは全てX[i]を選べば良い.
その他のケースについて,Z[i] := [0,i) で得られるM-1個以下の和の最大値 とする.
これは最小値を取り出すpriority_queueを用いれば更新できる.
sum _ ( 0 <= i < N ) Y [ i ] を求めておいて,以降X[i]を取るものを選び X[i] - Y[i]を足す.
i個目を最後に選ぶとそれ以降を取れなくなってしまうから, sum ( i < j < N ) ( Y [ i ] ) を引けば良く
後ろから X[i] - Y[i]+ Z[i] - sum_ ( i < j < N ) ( Y [ i ] )をの最大値を見ていけば良い.

メモ

M=1のケースに注意.
超典型っぽいのにseg木とか考えてやたら時間を使ってしまったので反省.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

priority_queue<int,vector<int>,greater<int>> que;
int X[MAX_N],Y[MAX_N],Z[MAX_N];

int main(){
  int N,M; cin >> N >> M;
  rep(i,N) scanf("%d%d",X+i,Y+i);
  int ans = 0;
  if(N<=M){
    rep(i,N) ans += X[i];
    cout << ans << endl;
    return 0;
  }
  rep(i,N) ans += Y[i];
  int temp = 0; fill(Z,Z+N,0);
  rep(i,M-1) que.push(X[i]-Y[i]), temp += X[i] - Y[i];
  // Z[i] := [0,i) から M-1個 とった時のmax(sum(X[j]-Y[j]))
  if(M>1){
    REP(i,M-1,N){
      Z[i] = temp;
      if(que.top()<X[i]-Y[i]){
        temp += X[i]-Y[i]-que.top();
        que.pop(); que.push(X[i]-Y[i]);
      }
    }
  }
  temp = 0; int ma = -INF;
  RREP(i,N-1,M-1){
    ma = max(ma,X[i]-Y[i]+Z[i]-temp);
    temp += Y[i];
  }
  cout << ans + ma << endl;
  return 0;
}