oj.uz

Submission #259324

# Submission time Handle Problem Language Result Execution time Memory
259324 2020-08-07T14:45:56 Z b00n0rp Hotel (CEOI11_hot) C++17
100 / 100
 1400 ms 51444 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define all(v) v.begin(),v.end()
#define remax(a,b) a = max(a,(int)(b))
#define pii pair<int,int>
#define F first
#define S second

const int MX = 300005;

int n,m,o;
priority_queue<int> pq;
vector<pair<pii,int> > v; // {{capacity,type},cost}
vi ans;

signed main(){
	cin >> n >> m >> o;
	REP(i,n){
		int x,y; cin >> x >> y;
		v.pb({{y,1},x});
	}
	REP(i,m){
		int x,y; cin >> x >> y;
		v.pb({{y,0},x});
	}
	sort(all(v));
	REP(i,n+m){
		if(v[i].F.S == 0){
			pq.push(v[i].S);
		}
		else{
			if(pq.empty()) continue;
			ans.pb(-pq.top()+v[i].S);
			pq.pop();
		}
	}
	int res = 0;
	sort(all(ans));
	REP(i,min((int)ans.size(),o)){
		if(ans[i] >= 0) break;
		res -= ans[i];
	}
	cout << res << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1216 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 4968 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 9288 KB Output is correct
2 Correct 131 ms 5472 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1147 ms 41960 KB Output is correct
2 Correct 1153 ms 42020 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1251 ms 47948 KB Output is correct
2 Correct 1400 ms 51444 KB Output is correct
3 Correct 1262 ms 48372 KB Output is correct