読者です 読者をやめる 読者になる 読者になる

日々精進

aikoと旅行とプログラミング

【AOJ 2019】Princess's Marriage

問題

Princess's Marriage | Aizu Online Judge

ソースコード

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>

using namespace std;

#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define pii pair<int, int>
#define pb push_back

#define N 10000

bool comp(pii left, pii right){
  if(left.second > right.second){
    return true;
  }else{
    return false;
  }
}


int main(){
  int n, m;
  while(cin >> n >> m, n||m){
    vector<pii> v(N);
    int d, p;
    rep(i, n){
      cin >> d >> p;
      v.pb(pii(d, p));
    }

    sort(v.begin(), v.end(), comp);
    
    rep(i, n){
      if(v[i].first > m){
        v[i].first -= m;
        break;
      }else{
        m -= v[i].first;
        v[i].first = 0;
      }
    }
    int e=0;
    rep(i, v.size()){
      e += (v[i].first * v[i].second);
    }

    cout << e << endl;
  }
  
}

ソートして期待値の高いものから雇っていくようにすればよい。コードが汚い。