oj.uz

Submission #118904

# Submission time Handle Problem Language Result Execution time Memory
118904 2019-06-20T01:12:00 Z tmwilliamlin168 Hotel (CEOI11_hot) C++14
100 / 100
 700 ms 50992 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=5e5;
int n, m, o, c[mxN], p[mxN], p2[mxN], a[mxN];
vector<int> va[mxN], vb[mxN+1];
priority_queue<int> pq;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> o;
	for(int i=0; i<n; ++i)
		cin >> c[i] >> p[i];
	memcpy(p2, p, 4*n);
	sort(p2, p2+n);
	for(int i=0; i<n; ++i) {
		p[i]=lower_bound(p2, p2+n, p[i])-p2;
		va[p[i]].push_back(c[i]);
	}
	for(int i=0, d, v; i<m; ++i) {
		cin >> d >> v;
		vb[lower_bound(p2, p2+n, v)-p2].push_back(d);
	}
	for(int i=0; i<n; ++i)
		sort(va[i].begin(), va[i].end());
	for(int i=0, k=0; i<n; ++i) {
		for(int b : vb[i])
			pq.push(b);
		for(int j=0; j<va[i].size()&&pq.size()&&pq.top()>va[i][j]; ++j) {
			a[k++]=pq.top()-va[i][j];
			pq.pop();
		}
	}
	nth_element(a, a+o, a+min(n, m), greater<int>());
	cout << accumulate(a, a+o, 0ll);
}

Compilation message

hot.cpp: In function 'int main()':
hot.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<va[i].size()&&pq.size()&&pq.top()>va[i][j]; ++j) {
                ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23908 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24316 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 25192 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 25976 KB Output is correct
2 Correct 66 ms 25464 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 29336 KB Output is correct
2 Correct 117 ms 27488 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 34724 KB Output is correct
2 Correct 682 ms 50992 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 37232 KB Output is correct
2 Correct 555 ms 37300 KB Output is correct
3 Correct 700 ms 40704 KB Output is correct