Submission #149068

#	Time	Username	Problem	Language	Result	Execution time	Memory
149068		=SUM(D1:D9) (#200)	십자가 놓기 (FXCUP4_cross)	C++17	100 / 100	240 ms	14428 KiB

cross

#include "cross.h"
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
multiset<long long> S; // keep as size K
vector<pair<int,int>> cross;
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int N = I.size();
	for(int i=0;i<N;++i){
		cross.push_back({I[i],O[i]});
	}
	sort(cross.begin(),cross.end(),[](auto x,auto y){return x.first>y.first;});
	long long mx=0;
	for(int i=0;i<N;++i){
		long long mi = cross[i].first;
		// put the O in the set
		S.insert(cross[i].second);
		// keep the size(evict the smallest o)
		if((int)S.size()>K) S.erase(S.begin());
		if((int)S.size()<K) continue;
		// get the smallest element
		long long statQuo = (int)(*S.begin());
		// update maxma
		if(mx < 2 * statQuo * mi - mi * mi){
			mx = 2 * statQuo * mi - mi * mi;
		}
	}

	return mx;
}

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