Submission #149052

#	Time	Username	Problem	Language	Result	Execution time	Memory
149052		본인 방금 올솔하는 상상함 (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	125 ms	6636 KiB

cross

#include "cross.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
pii ar[200010];
priority_queue<int, vector<int>, greater<int> > pq;

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int N = I.size();
	int i;
	for (i=0; i<N; i++) ar[i]={I[i], O[i]};
	sort(ar, ar+N);
	reverse(ar, ar+N);
	for (i=0; i<K; i++) pq.push(ar[i].second);
	long long ans=(2*pq.top()-ar[K-1].first)*(ll)ar[K-1].first;
	for (i=K; i<N; i++) {
		pq.pop();
		pq.push(ar[i].second);
		ans=max(ans, (2*pq.top()-ar[i].first)*(ll)ar[i].first);
	}
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 55 / 55
• Subtask 3: 37 / 37