Cod sursa(job #1391297)

Utilizator AndyCatrunaCatruna Andy AndyCatruna Data 17 martie 2015 19:59:45
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <fstream>
#define dim 100005
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,c[dim],P[dim],m[dim],d[dim],s,t,i,p,u,S;
int main(){
    fin>>n>>s>>t;
    for(i=1;i<=n;i++){
        fin>>c[i]>>P[i];
    }
    S+=c[1]*P[1];
    d[1]=1;
    p=1;u=1;
    for(i=2;i<=n;i++){
        while(p<=u && c[i]<=c[d[u]]+(i-d[u])*s){
            u--;
        }
        d[++u]=i;
        if(i-d[p]==t){
            p++;
        }
        S+=(c[d[p]]+(i-d[p])*s)*P[i];
    }
    fout<<S<<"\n";

    return 0;
}