oj.uz

Submission #118903

# Submission time Handle Problem Language Result Execution time Memory
118903 2019-06-20T01:08:55 Z tmwilliamlin168 Hotel (CEOI11_hot) C++14
100 / 100
 729 ms 66396 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

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:33: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 23936 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23936 KB Output is correct
2 Correct 23 ms 23904 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 25036 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 26064 KB Output is correct
2 Correct 69 ms 25436 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 29412 KB Output is correct
2 Correct 112 ms 27536 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 34764 KB Output is correct
2 Correct 657 ms 66396 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 37316 KB Output is correct
2 Correct 520 ms 56620 KB Output is correct
3 Correct 729 ms 57080 KB Output is correct