Submission #148636

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
148636	2019-09-01T04:49:37 Z	맞WATLE(#3593, arnold518, ksmzzang2003, songc)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	115 ms	8812 KB

cross

#include <bits/stdc++.h>
#include "cross.h"
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;

int N, K;
LL ans;
pii A[202020];
priority_queue<LL, vector<LL>, greater<LL>> PQ; 

long long SelectCross(int k, std::vector<int> I, std::vector<int> O) {
	N = I.size(), K = k;
	for (int i=1; i<=N; i++) A[i] = pii(I[i-1], O[i-1]);
	sort(A+1, A+N+1, [&](pii a, pii b){
		return a.first > b.first;
	});
	for (int i=1; i<=K; i++) PQ.push(A[i].second);
	ans = 2*A[K].first*PQ.top() - A[K].first*A[K].first;
	for (int i=K+1; i<=N; i++){
		PQ.push(A[i].second);
		PQ.pop();
		ans = max(ans, 2*A[i].first*PQ.top() - A[i].first*A[i].first);
	}
	return ans;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	12 ms	768 KB	Output is correct
6	Correct	111 ms	6760 KB	Output is correct
7	Correct	103 ms	6760 KB	Output is correct
8	Correct	108 ms	6764 KB	Output is correct

Subtask #2

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	12 ms	768 KB	Output is correct
6	Correct	111 ms	6760 KB	Output is correct
7	Correct	103 ms	6760 KB	Output is correct
8	Correct	108 ms	6764 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	6 ms	384 KB	Output is correct
12	Correct	12 ms	768 KB	Output is correct
13	Correct	61 ms	3692 KB	Output is correct
14	Correct	111 ms	6768 KB	Output is correct
15	Correct	108 ms	6852 KB	Output is correct
16	Correct	109 ms	6764 KB	Output is correct

Subtask #3

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	12 ms	768 KB	Output is correct
6	Correct	111 ms	6760 KB	Output is correct
7	Correct	103 ms	6760 KB	Output is correct
8	Correct	108 ms	6764 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	6 ms	384 KB	Output is correct
12	Correct	12 ms	768 KB	Output is correct
13	Correct	61 ms	3692 KB	Output is correct
14	Correct	111 ms	6768 KB	Output is correct
15	Correct	108 ms	6852 KB	Output is correct
16	Correct	109 ms	6764 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	6 ms	384 KB	Output is correct
19	Correct	13 ms	1024 KB	Output is correct
20	Correct	59 ms	3824 KB	Output is correct
21	Correct	87 ms	5484 KB	Output is correct
22	Correct	108 ms	6764 KB	Output is correct
23	Correct	115 ms	6848 KB	Output is correct
24	Correct	114 ms	7148 KB	Output is correct
25	Correct	115 ms	8804 KB	Output is correct
26	Correct	106 ms	8812 KB	Output is correct