Submission #834201

#	Time	Username	Problem	Language	Result	Execution time	Memory
834201		unnick	Crosses on the Grid (FXCUP4_cross)	C++17	0 / 100	1058 ms	25520 KiB

cross

#include "cross.h"
// #include <iostream>
#include <algorithm>
#include <queue>
#define ll long long

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

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int N = I.size();
	std::vector<int> idx;
	for (int i = 0; i < N; i++) {
		idx.push_back(i);
	}
	std::sort(idx.begin(), idx.end(), [I](int ia, int ib){
		return I[ia] > I[ib];
	});
	auto cmp = [O](int ia, int ib){
		return O[ia] > O[ib];
	};
	std::priority_queue<int, std::vector<int>, decltype(cmp)> queue(cmp);
	int ci = I[idx[K-1]];
	for(int i = 0; i < K; i++) {
		queue.push(idx[i]);
	}
	ll co = O[queue.top()];
	ll max_area = get_area(ci, co);
	for (int i = K; i < N; i++) {
		if (O[idx[i]] <= co) continue;
		queue.pop();
		queue.push(idx[i]);
		ci = I[idx[i]];
		co = O[queue.top()];
		ll area = get_area(ci, co);
		if (area > max_area) max_area = area;
	}
	return max_area;
}

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