5896번: Cow Coupons - 최적화 필요

https://www.acmicpc.net/problem/5896

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int MAX_N = 50000;
priority_queue<int> pq;
struct st {
    int p, c;
    bool operator<(st i) const {
        return p - c>i.p - i.c;
    }
}s[MAX_N];
int n, k, pcnt, res;
long long m, csum, psum;
pair<int, int> p[MAX_N];
bool ck[MAX_N];
int main() {
    scanf("%d %d %lld", &n, &k, &m);
    int i, j = 0;
    for (i = 0; i < n; i++)
        scanf("%d %d", &s[i].p, &s[i].c);
    sort(s, s + n);
    for (int i = 0; i < n; i++) p[i] = { s[i].p, i };
    sort(p, p + n);
    for (i = 0; i < n&&pq.size() < k; i++) {
        pq.push(s[i].c);
        csum += s[i].c;
        if (csum > m) {
            csum -= pq.top();
            pq.pop();
        }
        ck[i] = true;
    }
    res = pq.size();
    for (; i < n; i++) {
        for (; j < n; j++) {
            if (!ck[p[j].second]) {
                if (m - csum - psum < p[j].first) break;
                ck[p[j].second] = true;
                psum += p[j].first;
                pcnt++;
            }
        }
        res = max(res, k + pcnt);
        pq.push(s[i].c);
        csum += s[i].c - pq.top();
        pq.pop();
        if (ck[i]) {
            pcnt--;
            psum -= s[i].p;
        }
    }
    printf("%d", res);
    return 0;
}