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

AOJ 2019 Princess's Marriage

C/C++ AOJ

問題

Princess's Marriage

解法

距離と期待値を期待値の降順でソートしてどれだけ護衛を雇えるか計算する

心臓に悪いコード

int N, M;

bool cmp(const pi &a, const pi &b){
  return a.S > b.S;
}

int main(){
  int D, P;
  while(scanf("%d%d", &N, &M) && N+M){
    vector<pi>p(N);
    ll res = 0;
    rep(i, N){
      scanf("%d%d", &D, &P);
      p[i] = make_pair(D, P);
      res += D*P;
    }

    sort(p.begin(), p.end(), cmp);

    rep(i, N){
      if(p[i].F >= M){
    res -= M * p[i].S;
    M = 0;
      }else{
    res -= p[i].F * p[i].S;
    M -= p[i].F;
      }
      if(M == 0) break;
    }
    printf("%lld\n", res);
  }
  return 0;
}