Cod sursa(job #67600)

Utilizator sandyxpSanduleac Dan sandyxp Data 25 iunie 2007 12:29:31
Problema Branza Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 1.28 kb
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

#define FIN "branza.in"
#define FOUT "branza.out"
#define p1 first
#define p2 second

int n, s, t;
priority_queue < pair<int, int>, vector<pair<int,int> >, greater<pair<int, int> > > Q;

void citire()
{
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    scanf("%d %d %d", &n, &s, &t);
}

void rez()
{
    int i, c, p, cv;
    long long final = 0ll;
    // pentru a vedea care este costul minim daca as lua din una din zilele precedente, bagam intr-un heap
    // fiecare zi precedenta.. (si scoatem alea pt care "zi" < i-t)
    // si pt fiecare costul va fi s*(i-"zi") + costul_zilei_aleia...
    // cand bag prostii in heap, le pun dif. de timp = -i
    for (i=0; i<n; ++i) {
        scanf("%d %d", &c, &p);
        //fprintf(stderr, " > %d: top=(%d, %d) ", i, Q.top().first, Q.top().second);
        while (!Q.empty() && Q.top().second < i - t)
            Q.pop();
        if (!Q.empty())
            cv = min( Q.top().first + i * s, c );
        else cv = c;
        //fprintf(stderr, "cv=%d ", cv);
        Q.push(make_pair(c - s*i, i));
        //fprintf(stderr, " --- (%d, %d)\n", c-s*i, i);
        final += cv * p;
    }
    printf("%lld\n", final);
}

int main()
{
    citire();
    rez();
    return 0;
}