「HNOI2009 集训」KD之死

题目大意：

hzwer的题解

#include <cstdio>
#include <queue>
#include <algorithm>
 
typedef long long LL;
 
struct Node {
    LL w, t; bool f;
    bool operator < (const Node &rhs) const {
        return w + t < rhs.w + rhs.t;
    }
} a[600005];
 
int n, m, ans; LL sum, maxv;
 
std::priority_queue<LL> Q;
 
bool solve() {
    for (int i = 1; i <= n; ++i) {
        if (a[i].f) {
            while (sum > a[i].t) {
                if (Q.empty()) return false;
                sum -= Q.top(), Q.pop(), --ans;
            }
            sum += a[i].w, ++ans;
        } else {
            if (sum > a[i].t) {
                if (Q.top() < a[i].w || sum - Q.top() > a[i].t)
                    continue;
                sum -= Q.top(), Q.pop(), --ans;
            }
            sum += a[i].w, Q.push(a[i].w), ++ans;
        }
    }
    return true;
}
 
int main() {
    scanf("%d%d%lld", &n, &m, &maxv);
    for (int i = 1; i <= n; ++i)
        scanf("%lld%lld", &a[i].w, &a[i].t);
    for (int i = 1, j; i <= m; ++i)
        scanf("%d", &j), a[j].f = 1;
    std::sort(a + 1, a + n + 1);
    a[++n].f = 1, a[n].t = maxv;
    if (!solve()) puts("Foolish SD!");
    else printf("%d\n", ans - 1);
    return 0;
}