Cod sursa(job #1350790)

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

using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");
int 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]*P[i]<S*(i-D[u])*P[i]+C[D[u]]*P[i])
            u--;
        D[++u]=i;
        if(D[u]-D[p]>T)
            p++;
        sol+=C[D[p]]*P[D[u]]+S*(D[u]-D[p])*P[D[u]];
    }
    fout<<sol;
    fin.close();fout.close();
    return 0;
}