POJ(PKU) 3045 Cow Acrobats

普通に二分探索使わなくてもいいのでは？とおもって調べてみたら普通に貪欲法でいけるらしいです。

下のブログを参考にしました。

POJ-3045 : Cow Acrobats - komiyamの日記

#include <cstdio>
#include <algorithm>
#include <utility>

using namespace std;
int n;

typedef pair<int,int> P;
typedef pair<int,P> PP;


int main(){
  PP d[50002];
  int ans = -1000000000;
  scanf("%d",&n);
  
  for(int i = 0;i < n;i++){
    scanf("%d%d",&d[i].second.first,&d[i].second.second);
    d[i].first = d[i].second.first + d[i].second.second;
  }
  
  sort(d, d + n);
  int sum = 0;
  for(int i = 0;i < n;i++){
    ans = max(ans,sum - d[i].second.second);
    sum += d[i].second.first;
  }
  
  printf("%d\n",ans);
  
  return 0;
  
}