Cod sursa(job #1571049)

Utilizator Master011Dragos Martac Master011 Data 17 ianuarie 2016 01:05:02
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<cstdio>
using namespace std;

const int nMax = 100001;
long long c[nMax], dq[nMax];

int main (){
    FILE *in = fopen("branza.in","r");
    FILE *out = fopen("branza.out","w");

    long long n,s,t,p;
    fscanf(in,"%lld%lld%lld", &n, &s, &t);

    int st = 1 , dr = 0;
    long long cmin = 0;
    for(int i = 1 ; i <= n ; ++i){
        fscanf(in,"%lld%lld",&c[i], &p);

        while(st <= dr && c[dq[dr]] + s * (i - dq[dr]) > c[i]) dr--;
        dq[++dr] = i;
        if(st <= dr && dq[st] < i - t) st++;
        cmin += (c[dq[st]] + s * (i - dq[st])) * p;
    }

    fprintf(out,"%d\n", cmin);
    return 0;
}