Cod sursa(job #1113826)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 20 februarie 2014 22:26:09
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.49 kb
#include <fstream>

using namespace std;

ifstream fin ("branza.in");
ofstream fout ("branza.out");

long long sol,n,s,t,p,u,pi,i;
long long d[100010],v[100010];

int main () {

    fin>>n>>s>>t;

    p=1;u=0;

    for (i=1;i<=n;i++) {
        fin>>v[i]>>pi;
        while(p<=u && v[i]<=(v[d[u]]+s*(i-d[u])))
            u--;
        d[++u]=i;
        while (d[p]<i-t)
            p++;
        sol+= (v[d[p]]+s*(i-d[p]))*pi;
    }

    fout<<sol<<"\n";

    return 0;
}