Submission #115336

#	Time	Username	Problem	Language	Result	Execution time	Memory
115336		model_code	Hotel (CEOI11_hot)	C++17	50 / 100	4093 ms	29624 KiB

hot

/* Slow solution for task HOT
 * Author: Miroslaw Michalski
 * 24APR11
 * instead of `lower_bound` we use
 * linear search
 */
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
int main() {
  int n, m, o, ci, pi;
  long long res = 0;
  vector<int> think;
  map<pair<int, int>, int> v;
  scanf("%d%d%d", &n, &m, &o);
  for(int i = 0; i < n; i++) {
    scanf("%d%d", &ci, &pi);
    pair<int, int> obj = make_pair(pi, ci);

    if (v.find(obj) == v.end()) {
      v[obj] = 1;
    } else {
      v[obj]++;
    }
  }
  vector<pair<int, int> > q;
  for(int i = 0; i < m; i++) {
    scanf("%d%d", &ci, &pi);
    q.push_back(make_pair(ci, pi));
  }
  sort(q.begin(), q.end());
  reverse(q.begin(), q.end());
  
  for(int i = 0; i < m; i++) {
    ci = q[i].first;
    pi = q[i].second;
    for(map<pair<int, int>, int>::iterator it = v.begin();
        it != v.end();
        ++it) {
      if (it->first > make_pair(pi, -1)) {
        if ((it->first).second < ci) {
          think.push_back(ci - (it->first).second);
        }
        if (it->second == 1) {
          v.erase(it);
        } else {
          v[it->first] --;
        }
        break;
      }
    }
  }
  sort(think.begin(), think.end());
  reverse(think.begin(), think.end());
  o = min(o, static_cast<int>(think.size()));
  for(int i = 0; i < o; i++) {
    res += think[i];
  }
  printf("%lld\n", res);
}

Compilation message (stderr)

hot.cpp: In function 'int main()':
hot.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &m, &o);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
hot.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &ci, &pi);
     ~~~~~^~~~~~~~~~~~~~~~~~
hot.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &ci, &pi);
     ~~~~~^~~~~~~~~~~~~~~~~~

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