Submission #148688

#	Time	Username	Problem	Language	Result	Execution time	Memory
148688		USA1 (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	259 ms	14436 KiB

cross

#include "cross.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
long long SelectCross(int k, std::vector<int> a, std::vector<int> b) {
	vector<pair<int,int> > x;
	multiset<int> r;
	for(int i = 0; i < (int)a.size(); i++){
		x.push_back({a[i], b[i]});
	}
	sort(x.begin(), x.end());
	reverse(x.begin(), x.end());

	ll ans = 0;
	multiset<int> bb;
	for(pair<int,int> p : x){
		bb.insert(p.second);
		while((int)bb.size() > k) bb.erase(bb.begin());
		if((int)bb.size() == k){
			ll A = p.first;
			ll B = *bb.begin();
			ans = max(ans, 2 * A * B - A * A);
		}
	}
	return ans;
}

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