Submission #148750

#	Time	Username	Problem	Language	Result	Execution time	Memory
148750		Powered By Zigui (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	287 ms	19176 KiB

cross

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

using namespace std;

typedef long long ll; 
typedef pair<ll, ll> pll;

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int N = I.size();
	vector<pll> V;	V.resize(N);
	for(int i = 0 ; i < N ; i++) V[i].first = I[i], V[i].second = O[i];
	sort(V.begin(), V.end());
	reverse(V.begin(), V.end());

	int cnt = 0;
	map<ll, int> MP;
	long long ans = 0;
	for(int i = 0 ; i < N ; i++){
		if(cnt == K) {
			MP.begin()->second--;	cnt--;
			if(MP.begin()->second == 0) MP.erase(MP.begin());
		}

		MP[V[i].second]++;	cnt++;
		if(cnt == K){
			ans = max(ans, V[i].first * V[i].first + (MP.begin()->first - V[i].first) * V[i].first * 2);
		}
	}	
	return ans;
}

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