oj.uz

Submission #104600

# Submission time Handle Problem Language Result Execution time Memory
104600 2019-04-08T10:09:15 Z DMCS Kisik (COCI19_kisik) C++14
90 / 90
 447 ms 36648 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define w first 
#define h second 
typedef pair<int, int> rect;
const int N = 1e6;

bool cmp(rect r1, rect r2) {
	return r1.h < r2.h;
}

rect b[N];
priority_queue<int> wd;

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++) cin >> b[i].w >> b[i].h;
	sort(b, b+n, cmp);
	int ans, temp = 0;
	for(int i = 0; i < k-1; i++) {
		temp += b[i].w;
		wd.push(b[i].w);
	} 
	ans = (temp + b[k-1].w) * b[k-1].h; 
	for(int i = k; i < n; i++) {
		temp += b[i-1].w;
		wd.push(b[i-1].w);
		temp -= wd.top();
		wd.pop();
		int s = (temp + b[i].w) * b[i].h;
		ans = min(ans, s);
	} 
	cout << ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 9080 KB Output is correct
2 Correct 294 ms 22764 KB Output is correct
3 Correct 228 ms 26356 KB Output is correct
4 Correct 204 ms 24808 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 14956 KB Output is correct
2 Correct 29 ms 3828 KB Output is correct
3 Correct 56 ms 7024 KB Output is correct
4 Correct 194 ms 18640 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 9684 KB Output is correct
2 Correct 231 ms 16228 KB Output is correct
3 Correct 177 ms 12532 KB Output is correct
4 Correct 388 ms 36648 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 11628 KB Output is correct
2 Correct 447 ms 30404 KB Output is correct
3 Correct 105 ms 10484 KB Output is correct
4 Correct 248 ms 28388 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 20596 KB Output is correct
2 Correct 236 ms 22252 KB Output is correct
3 Correct 185 ms 18640 KB Output is correct
4 Correct 140 ms 13776 KB Output is correct