Submission #832541

#	Time	Username	Problem	Language	Result	Execution time	Memory
832541		Liudas	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	73 ms	11932 KiB

cross

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
struct cross{
    int i, o;
    long long s;
};
long long SelectCross(int K, vector<int> I, vector<int> O){
    int N = I.size();
    vector<cross> arr(N);
    for(int i = 0; i < N;  i++){
        arr[i] = {I[i], O[i], 1ll * I[i] * O[i] * 2 - 1ll * I[i] * I[i]};
    }
    sort(arr.begin(), arr.end(), [](cross a, cross b){return make_pair(a.i, a.o) > make_pair(b.i, b.o);});
    priority_queue<int, vector<int>, greater<int>> que;
    for(int i = 0; i < K-1; i ++){
        que.push(arr[i].o);
    }
    long long ans = 0;
    for(int i = K-1; i < N; i ++){
        que.push(arr[i].o);
        int a = que.top();
        que.pop();
        ans = max(ans, 1ll * arr[i].i * a * 2 - 1ll * arr[i].i * arr[i].i);
    }
    return ans;
}

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