Cod sursa(job #1940056)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 26 martie 2017 12:59:56
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>

using namespace std;
int n,s,t,i,p,u,sol,c[100001],P[100001],d[100001];
ifstream fin ("branza.in");
ofstream fout ("branza.out");

int main (){

    fin>>n>>s>>t;
    for (i=1;i<=n;i++)
        fin>>c[i]>>P[i];
    d[1] = 1;
    p = 1; u = 1;
    sol += ( c[d[p]] + (1-d[p])*s ) * P[1];
    for (i=2;i<=n;i++){
        while (p<=u && c[i] <= c[d[u]] + s*(i-d[u]))
            u--;
        d[++u] = i;
        if (i-d[p] == t+1)
            p++;
        sol += ( c[d[p]] + (i-d[p])*s ) * P[i];
    }
    fout<<sol;


    return 0;
}