Cod sursa(job #1943265)

Utilizator Liviu_Ionut_MoantaMoanta Ionut Liviu Liviu_Ionut_Moanta Data 28 martie 2017 14:38:19
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include<fstream>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,s,t,i,p1,u,q;
int c[100003],p[100003],v[100003];
int main(){
    fin>>n>>s>>t;
    for(i=1;i<=n;i++){
        fin>>c[i]>>p[i];
    }
    v[1]=1;
    p1=1;
    u=1;
    q=c[1]*p[1];
    for(i=2;i<=n;i++){
        while(p1<=u&&c[i]<=c[v[u]]+s*(i-v[u])){
            u--;
        }
        v[++u]=i;
        if(i-v[p1]==t+1){
            p1++;
        }
        q+=(c[v[p1]]+(i-v[p1])*s)*p[i];
    }
    fout<<q;
    return 0;
}