Submission #115328

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
115328	2019-06-06T17:24:10 Z	model_code	Hotel (CEOI11_hot)	C++17	100 / 100	1744 ms	39776 KB

/* Model solution for task HOT
 * Author: Miroslaw Michalski
 * Time complexity : O(n log n)
 * 24APR11
 * pure STL stuff
 */
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>

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 j = 0; j < m; j++) {
    int vj, dj;
    scanf("%d%d", &vj, &dj);
    q.push_back(make_pair(vj, dj));
  }
  sort(q.begin(), q.end());
  reverse(q.begin(), q.end());
  
  for(int j = 0; j < m; j++) {
    int vj = q[j].first;
    int dj = q[j].second;
    map<pair<int, int>, int>::iterator it = v.lower_bound(make_pair(dj, -1));
    if (it != v.end()) {
      if ((it->first).second < vj) {
        think.push_back(vj - (it->first).second);
      }
      if (it->second == 1) {
        v.erase(it);
      } else {
        v[it->first] --;
      }
    }
  }
  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);
  return 0;
}

Compilation message

hot.cpp: In function 'int main()':
hot.cpp:20: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:22: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:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &vj, &dj);
     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	300 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1024 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	3536 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	118 ms	5852 KB	Output is correct
2	Correct	90 ms	5308 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	469 ms	15964 KB	Output is correct
2	Correct	179 ms	8460 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1061 ms	31700 KB	Output is correct
2	Correct	1251 ms	29740 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	957 ms	23820 KB	Output is correct
2	Correct	1381 ms	39184 KB	Output is correct
3	Correct	1744 ms	39776 KB	Output is correct