제출 #1364383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364383		saywoo	Grilled Bottle (KAISTRUN26SPRING_D)	C++20	100 / 100	403 ms	10228 KiB

Main

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

using ll = long long int;
using pr = pair<ll, ll>;
#define x first
#define y second

ll n, m;
vector<pr> a, b;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    a.resize(n); b.resize(m);
    for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
    for (int i = 0; i < m; i++) {
        cin >> b[i].x;
        b[i].y = i + 1;
    }

    sort(a.begin(), a.end(), greater<pr>());
    sort(b.begin(), b.end(), greater<pr>());

    ll l = 0; ll r = m + 1;
    ll ans = 0;

    while (l + 1 < r) {
        ll mid = (l + r) >> 1;

        bool ok = true;
        ll s = 0;
        ll ptr = 0;
        priority_queue<ll> pq;
        for (auto [val, idx]: b) {
            if (idx > mid) continue;

            while (ptr < n) {
                if (val <= a[ptr].x) {
                    pq.push(a[ptr].y);
                    ptr++;
                }
                else break;
            }

            if (pq.empty()) {
                ok = false; break;
            }
            else {
                s += pq.top();
                pq.pop();
            }
        }

        if (ok) {
            l = mid;
            ans = s;
        }
        else r = mid;
    }

    cout << l << " " << ans << '\n';

    return 0;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 20 / 20
• 서브태스크 3: 30 / 30
• 서브태스크 4: 40 / 40