oj.uz

Submission #834201

# Submission time Handle Problem Language Result Execution time Memory
834201 2023-08-22T11:50:37 Z unnick Crosses on the Grid (FXCUP4_cross) C++17
0 / 100
 1000 ms 25520 KB 
#include "cross.h"
// #include <iostream>
#include <algorithm>
#include <queue>
#define ll long long

ll get_area(ll i, ll o) {
	return i*(o*2-i);
}

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int N = I.size();
	std::vector<int> idx;
	for (int i = 0; i < N; i++) {
		idx.push_back(i);
	}
	std::sort(idx.begin(), idx.end(), [I](int ia, int ib){
		return I[ia] > I[ib];
	});
	auto cmp = [O](int ia, int ib){
		return O[ia] > O[ib];
	};
	std::priority_queue<int, std::vector<int>, decltype(cmp)> queue(cmp);
	int ci = I[idx[K-1]];
	for(int i = 0; i < K; i++) {
		queue.push(idx[i]);
	}
	ll co = O[queue.top()];
	ll max_area = get_area(ci, co);
	for (int i = K; i < N; i++) {
		if (O[idx[i]] <= co) continue;
		queue.pop();
		queue.push(idx[i]);
		ci = I[idx[i]];
		co = O[queue.top()];
		ll area = get_area(ci, co);
		if (area > max_area) max_area = area;
	}
	return max_area;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 284 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 27 ms 1740 KB Output is correct
6 Execution timed out 1058 ms 25520 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 284 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 27 ms 1740 KB Output is correct
6 Execution timed out 1058 ms 25520 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 284 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 27 ms 1740 KB Output is correct
6 Execution timed out 1058 ms 25520 KB Time limit exceeded
7 Halted 0 ms 0 KB -