Submission #149419

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

cross

#include "cross.h"
#include <algorithm>
#include <utility>
#include <set>

std::vector<std::pair<int, int> > p;
std::multiset<int> st;

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int N = I.size();
	for (int i = 0; i < N; i++)
		p.push_back(std::make_pair(O[i], I[i]));
	std::sort(p.begin(), p.end()); std::reverse(p.begin(), p.end());
	for (int i = 0; i < K - 1; i++) 
		st.insert(p[i].second);
	st.insert(2000000000);
	auto si = st.begin();
	long long ans = 0;
	for (int i = K - 1; i < N; i++) {
		int t = p[i].first - std::min((*si), p[i].second);
		ans = std::max(ans, 1LL * p[i].first * p[i].first - 1LL * t * t);
		if (p[i].second >(*si)) {
			st.insert(p[i].second); ++si;
		}
	}
	return ans;
}

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