Submission #150267

#	Time	Username	Problem	Language	Result	Execution time	Memory
150267		TeamSUA (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	134 ms	6880 KiB

cross

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

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()

using namespace std;
using namespace placeholders;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <class T> inline void mini(T &l, T r){l = min(l, r);}
template <class T> inline void maxi(T &l, T r){l = max(l, r);}

template <class it> auto gr(it b, it e){
    return vector<typename remove_reference<decltype(*b)>::type>(b, e);
}
template <class T> void _dbg(const char *sdbg, T h){cerr << sdbg << "=" << h << "\n";}
template <class T, class ...R> void _dbg(const char *sdbg, T h, R... a){
	while (*sdbg != ','){cerr << *sdbg++;}cerr << "=" << h << ","; _dbg(sdbg + 1, a...);
}
template <class T> ostream &operator <<(ostream &os, vector<T> v){
	os << "["; for (auto x: v) os << x << ","; return os << "]";
}
template <class L, class R> ostream &operator <<(ostream &os, pair<L, R> P){
	return os << "(" << P.st << "," << P.nd << ")";
}

#ifndef ONLINE_JUDGE
#define eput(...) do{cerr << __LINE__;_dbg("\t| "#__VA_ARGS__, __VA_ARGS__);}while(0)
#else
#define eput(...) 218
#endif

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	typedef long long ll;
	int N = I.size();

	vector<pair<int, int>> a;
	for (int i = 0; i < N; ++i)
		a.emplace_back(I[i], O[i]);
	sort(a.begin(), a.end(), greater<pair<int, int>>());

	priority_queue<int, vector<int>, greater<int>> Q;
	for (int i = 0; i < K; ++i)
		Q.emplace(a[i].second);

	ll ans = (ll)a[K - 1].first * (Q.top() * 2 - a[K - 1].first);
	for (int i = K; i < N; ++i){
		Q.emplace(a[i].second);
		Q.pop();

		ans = max(ans, (ll)a[i].first * (Q.top() * 2 - a[i].first));
	}
	return ans;
}

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