1R/2016 09 24

오늘의 문제

• 도둑

코드

15이원준

#include<iostream>
#include<algorithm>
#include<set>
#include<utility>
#include<queue>

using namespace std;

int main(){
  priority_queue<pair<int, int>> que;
  multiset<int> bag;
  int N, K;
  long long int ans = 0;
  cin >> N >> K;
  for(int i = 0; i<N; i++){
    int tmp1, tmp2;
    scanf("%d %d", &tmp1, &tmp2);
    que.push(make_pair(tmp2, tmp1));
  }
  for(int i = 0; i<K; i++){
    int tmp;
    scanf("%d", &tmp);
    bag.insert(tmp);
  }
  while(que.size() && bag.size()){
    pair<int,int> tmp = que.top();
    que.pop();
    auto p = bag.lower_bound(tmp.second);
    if(p != bag.end()){
      ans+= tmp.first;
      bag.erase(p);
    }
  }
  cout<< ans<<endl;
}

아이디어

15이원준

• 가치가 큰 보석 부터 넣을 수 있는 가장 작은 가방에 차례대로 넣는다.
• 끝
• 가치는 1 ≤ V ≤ 1,000,000이고 보석 수는 1 ≤ N ≤ 300,000이기 때문에 int범위를 벗어 날 수 있으니 주의 해야한다.