[JOI精進録] 難易度7「美術展」(JOI2017/2018 本選B)

問題リンク

atcoder.jp

問題概要

個の品物 ( )があり、それぞれに大きさと価値が定められている。
この中からいくつかの品物を選び、価値の総和-(大きさの最大値-大きさの最小値)を最大化してください。

解説

AC解法(100/100点)

価値の総和を、大きさの最大値を、最小値をとします。



はどのでも同じように増えていくので、最大値を全探索して 今までのの最大値と現在探索中の値を比較更新していけばよいです。

ACコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin >> n;
  map<long long,long long> M;
  long long t=0,r=0,a,b;
  while(n--) (cin>>a>>b),M[a]+=b;
  for (auto [a,b]:M) t = max(t,a),t += b,r = max(r,t-a);
  cout << r << endl;
}

提出結果

atcoder.jp