oj.uz

Submission #150878

# Submission time Handle Problem Language Result Execution time Memory
150878 2019-09-01T09:52:02 Z gs14004 Crosses on the Grid (FXCUP4_cross) C++17
100 / 100
 118 ms 10724 KB 
#include "cross.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 200005;
 
int N;
lint X[MAXN], Y[MAXN];
 
lint func(lint X, lint Y){
	return 2 * X * Y - X * X;
}
 
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	N = I.size();
	vector<pi> v, A;
	for(int i=0; i<N; i++) v.emplace_back(I[i], O[i]);
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	priority_queue<int, vector<int>, greater<int> > pq;
	lint ret = 0;
	for(int i=0; i<sz(v); ){
		int e = i;
		while(e < sz(v) && v[i].first == v[e].first) e++;
		for(int j=i; j<e; j++) pq.push(v[j].second);
		while(sz(pq) > K) pq.pop();
		if(sz(pq) == K) ret = max(ret, func(v[i].first, pq.top()));
		i = e;
	}
	return ret;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 106 ms 9464 KB Output is correct
7 Correct 106 ms 9532 KB Output is correct
8 Correct 106 ms 9572 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 106 ms 9464 KB Output is correct
7 Correct 106 ms 9532 KB Output is correct
8 Correct 106 ms 9572 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 252 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 8 ms 1016 KB Output is correct
13 Correct 56 ms 5108 KB Output is correct
14 Correct 106 ms 9520 KB Output is correct
15 Correct 107 ms 9440 KB Output is correct
16 Correct 108 ms 9612 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 106 ms 9464 KB Output is correct
7 Correct 106 ms 9532 KB Output is correct
8 Correct 106 ms 9572 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 252 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 8 ms 1016 KB Output is correct
13 Correct 56 ms 5108 KB Output is correct
14 Correct 106 ms 9520 KB Output is correct
15 Correct 107 ms 9440 KB Output is correct
16 Correct 108 ms 9612 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 9 ms 1144 KB Output is correct
20 Correct 59 ms 5036 KB Output is correct
21 Correct 86 ms 8060 KB Output is correct
22 Correct 110 ms 9484 KB Output is correct
23 Correct 114 ms 9556 KB Output is correct
24 Correct 118 ms 9484 KB Output is correct
25 Correct 117 ms 10416 KB Output is correct
26 Correct 109 ms 10724 KB Output is correct