Cod sursa(job #659648)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 10 ianuarie 2012 20:19:35
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>
#include <deque>
#define NMAX 100001
using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

long long n,c[NMAX],p[NMAX],i,s,cost,t;
deque<long long> D;

void pop(int i) {
    while (!D.empty() && i-D.front()>t) D.pop_front();
}
void push(int i) {
    while (!D.empty() && c[D.back()]+(i-D.back())*s>=c[i]) D.pop_back();
    D.push_back(i);
}

int main () {
    f >> n >> s >> t;
    for (i=1;i<=n;i++) {
        f >> c[i] >> p[i];
        pop(i);push(i);
        cost+=(c[D.front()]+(i-D.front())*s)*p[i];
    }
    g << cost << '\n';
    f.close();g.close();
    return 0;
}