Submission #759939

#	Time	Username	Problem	Language	Result	Execution time	Memory
759939		jk410	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	66 ms	12620 KiB

cross

#include <bits/stdc++.h>
#include "cross.h"
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;

ll calc(ll i, ll o) {
	return 2 * o * i - i * i;
}

ll SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int n = (int)I.size();
	vector<pair<ll,ll>> c(n);
	for (int i = 0; i < n; i++)
		c[i] = { I[i],O[i] };
	sort(all(c));
	reverse(all(c));
	priority_queue<ll> q;
	for (int i = 0; i < K; i++)
		q.push(-c[i].second);
	ll ret = calc(c[K - 1].first, -q.top());
	for (int i = K; i < n; i++) {
		q.push(-c[i].second);
		q.pop();
		ret = max(ret, calc(c[i].first, -q.top()));
	}
	return ret;
}

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