Official

C - Cheese Editorial by en_translator


Basically, it is optimal to use cheese with more deliciousness per gram first, in order.
First, sort cheese in the decreasing order of deliciousness. Then, use cheese in order as much as possible.
Specifically, do the following in the decreasing order of deliciousness of cheese.

  • When we need \(w\) gram of more cheese, and \(B_k\) gram of currently focusing cheese remains, then use \(\min(w,B_k)\) gram of that cheese.

Sample code (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,w;
  cin >> n >> w;
  vector<pair<long long,long long>> v(n);
  for(auto &nx : v){
    cin >> nx.first >> nx.second;
  }
  sort(v.begin(),v.end());
  reverse(v.begin(),v.end());
  long long res=0;
  for(auto &nx : v){
    res+=nx.first*min(w,nx.second);
    w-=min(w,nx.second);
  }
  cout << res << '\n';
  return 0;
}

posted:
last update: