Submission #148636

#	Time	Username	Problem	Language	Result	Execution time	Memory
148636		맞WATLE (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	115 ms	8812 KiB

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 / 8
• Subtask 2: 55 / 55
• Subtask 3: 37 / 37