Submission #229495

#	Time	Username	Problem	Language	Result	Execution time	Memory
229495		anayk	Hotel (CEOI11_hot)	C++14	100 / 100	1694 ms	58744 KiB

hot

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define int long long

signed main()
{
  int n, m, o;
  std::cin >> n >> m >> o;

  std::vector<std::pair<int, int> > rooms(n);
  for(int i = 0; i < n; i++) {
    std::cin >> rooms[i].second >> rooms[i].first;
  }

  std::vector<std::pair<int, int> > cust(m);
  for(int i = 0; i < m; i++) {
    std::cin >> cust[i].second >> cust[i].first;
  }

  std::sort(cust.begin(), cust.end());
  std::sort(rooms.begin(), rooms.end());

  std::multiset<int> avail;
  std::multiset<int> cand;
  
  int j = 0;
  for(int i = 0; i < n; i++) {
    while(j < m && cust[j].first <= rooms[i].first) {
      avail.insert(-cust[j].second);
      j++;
    }

    if(!avail.empty()) {
      cand.insert((*avail.begin()) + rooms[i].second);
      avail.erase(avail.begin());
    }
  }

  int ans = 0;
  while(!cand.empty() && o > 0) {
    if(*cand.begin() >= 0)
      break;
    ans -= *cand.begin();
    cand.erase(cand.begin());
    o--;
  }

  std::cout << ans << std::endl;

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10