Cod sursa(job #1350796)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 20 februarie 2015 22:47:20
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include <fstream>
#define DIM 100002

using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");
long long N,S,T,C[DIM],P[DIM],D[DIM],p,u,sol;
int main(){
    fin>>N>>S>>T;
    for(int i=1;i<=N;i++)
        fin>>C[i]>>P[i];
    p=1;
    for(int i=1;i<=N;i++){
        while(p<=u && C[i]<S*(i-D[u])+C[D[u]])
            u--;
        D[++u]=i;
        if(i-D[p]>T)
            p++;
        sol+=C[D[p]]*P[i]+S*(i-D[p])*P[i];
    }
    fout<<sol<<"\n";
    fin.close();fout.close();
    return 0;
}