Cod sursa(job #1943297)

Utilizator Liviu_Ionut_MoantaMoanta Ionut Liviu Liviu_Ionut_Moanta Data 28 martie 2017 14:56:57
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<fstream>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
long long n,s,t,i,p1,u,q;
long long 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--;
        }
        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;
}