Submission #832501

#	Time	Username	Problem	Language	Result	Execution time	Memory
832501		gustason	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	101 ms	18212 KiB

cross

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

using namespace std;

using ll = long long;

ll sq(int x) {
	return (ll) x * x;
}

ll plotas(int r, int R) {
	return sq(R) - sq(R-r);
}

ll SelectCross(int k, std::vector<int> r, std::vector<int> R) {
	int n = r.size();
	
	ll ans = 0;
	//for(int i = 0; i < n; i++) {
		//ans = max(ans, plotas(r[i], R[i]));
	//}
	
	vector<pair<int, int>> a(n);
	for(int i = 0; i < n; i++) {
		a[i] = {R[i], r[i]};
	}
	
	multiset<int> st;
	
	auto rem = [&](int x) {
		st.erase(st.find(x));
	};
	
	sort(a.rbegin(), a.rend());
	
	for(int i = 0; i < n; i++) {
		if ((int) st.size() < k) {
			st.insert(a[i].second);
		}
		else {
			if (*st.begin() < a[i].second) {
				rem(*st.begin());
				st.insert(a[i].second);
			}
		}
		
		if ((int) st.size() == k) {
			ans = max(ans, plotas(*st.begin(), a[i].first));
			//cout << a[i].first << " " << *st.begin() << " " << plotas(*st.begin(), a[i].first) << "\n";
		}
	}
	
	return ans;
}
	

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