Submission #113019

#	Time	Username	Problem	Language	Result	Execution time	Memory
113019		imsifile	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	93 ms	8812 KiB

cross

#include "cross.h"
#include <algorithm>
#include <queue>
using namespace std;

typedef long long lld;

struct cross {
	lld in, ou;
	bool operator< (const cross& c) const {
		return ou > c.ou;
	}
} ba[202020];

priority_queue<lld> pq;

lld SelectCross(int N, int K, vector<int> I, vector<int> O) {
	for(int i=0; i<N; i++) ba[i].in=I[i], ba[i].ou=O[i];
	sort(ba, ba+N);
	lld mx=0;
	for(int i=0; i<N; i++){
		pq.push(-ba[i].in);
		if(i>=K) pq.pop();
		if(i>=K-1){
			lld ii=-pq.top(), oo=ba[i].ou;
			if(mx < 2*ii*oo-ii*ii) mx = 2*ii*oo-ii*ii;
		}
	}
	return mx;
}

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