Submission #832501

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
832501	2023-08-21T10:56:43 Z	gustason	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	101 ms	18212 KB

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.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	304 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	3 ms	724 KB	Output is correct
6	Correct	53 ms	8904 KB	Output is correct
7	Correct	69 ms	8924 KB	Output is correct
8	Correct	53 ms	8984 KB	Output is correct

Subtask #2

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	304 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	3 ms	724 KB	Output is correct
6	Correct	53 ms	8904 KB	Output is correct
7	Correct	69 ms	8924 KB	Output is correct
8	Correct	53 ms	8984 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	296 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	4 ms	808 KB	Output is correct
13	Correct	27 ms	4760 KB	Output is correct
14	Correct	53 ms	8908 KB	Output is correct
15	Correct	56 ms	9196 KB	Output is correct
16	Correct	62 ms	8936 KB	Output is correct

Subtask #3

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	304 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	3 ms	724 KB	Output is correct
6	Correct	53 ms	8904 KB	Output is correct
7	Correct	69 ms	8924 KB	Output is correct
8	Correct	53 ms	8984 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	296 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	4 ms	808 KB	Output is correct
13	Correct	27 ms	4760 KB	Output is correct
14	Correct	53 ms	8908 KB	Output is correct
15	Correct	56 ms	9196 KB	Output is correct
16	Correct	62 ms	8936 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	5 ms	1428 KB	Output is correct
20	Correct	30 ms	5064 KB	Output is correct
21	Correct	41 ms	7096 KB	Output is correct
22	Correct	52 ms	8888 KB	Output is correct
23	Correct	57 ms	8976 KB	Output is correct
24	Correct	71 ms	10256 KB	Output is correct
25	Correct	90 ms	14984 KB	Output is correct
26	Correct	101 ms	18212 KB	Output is correct