Cod sursa(job #1679053)

Utilizator akaprosAna Kapros akapros Data 7 aprilie 2016 17:36:25
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
int n, x, l;
struct s
{
    int x, y;
}v[maxN];
bool used[maxN];
long long ans;
int cmp(const s a, const s b)
{
    return a.x < b.x;
}
priority_queue < int > q;
void read()
{
    int i, m = 0;
    freopen("lupu.in", "r", stdin);
    scanf("%d %d %d", &n, &x, &l);
    for (i = 1; i <= n; ++ i)
    {
        int d, a;
        scanf("%d %d", &d, &a);
        if (d <= x)
        {
            ++ m;
            v[m].x = d;
            v[m].y = a;
        }
    }
    n = m;
}
void brut()
{
    int i, a = 1, xx = 0;
    while (xx <= x && a)
    {
        a = 0;
        for (i = 1; i <= n; ++ i)
            if (!used[i] && v[i].x <= xx && v[i].y >= v[a].y)
               a = i;
        if (a)
        {
            used[a] = 1;
            ans += 1LL * v[a].y;
        }
        xx += l;
    }
}
void optim()
{
    int i = 1, xx;
    sort(v + 1, v + n + 1, cmp);
    xx = v[1].x - l + 1;
    while (xx <= x && i <= n)
    {
        ans += q.top();
        q.pop();
        int p = v[i].x;
        while (v[i].x <= xx + l && v[i].x > xx)
        {
            q.push(v[i].y);
            ++ i;
        }
        xx = max(v[p].x - l, xx + l);
    }
}
void solve()
{
    if (n <= 1000)
    brut();
}
void write()
{
    freopen("lupu.out", "w", stdout);
    printf("%lld\n", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}