제출 #149156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
149156		본인 하지만 안 어림 ㅋㅋ (#200)	십자가 놓기 (FXCUP4_cross)	C++17	100 / 100	127 ms	6876 KiB

cross

#include <bits/stdc++.h>
using namespace std;

#include "cross.h"

struct pos
{
    int x, y;
    bool operator <(const pos &a) const
    {
        return x != a.x ? x > a.x : y > a.y;
    }
};

long long SelectCross(int k, std::vector<int> I, std::vector<int> O) {
    int n = I.size(), i;

    vector<pos> v;
    for(i = 0; i < n; i++)
        v.push_back({ O[i], I[i] });

    sort(v.begin(), v.end());

    long long res = 0;
    priority_queue<int> pq;
    for(i = 0; i < n; i++)
    {
        pq.push(-v[i].y);

        while((int)pq.size() > k)
            pq.pop();

        if((int)pq.size() == k)
        {
            int x = v[i].x;
            int y = -pq.top();

            long long cur = 2LL * x * y - 1LL * y * y;
            res = max(res, cur);
        }
    }

    return res;
}

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