Cod sursa(job #2072798)

Utilizator vladstanciuVlad Stanciu vladstanciu Data 22 noiembrie 2017 11:27:41
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int d[100000],c[100000];

int main()
{
    int n,t,i,st,dr,p;
    long long s, sum;
    in>>n>>s>>t;
    t++;
    sum = 0;
    st = 0;
    dr = 0;
    for( i = 0; i < n; i++ ){
        in>>c[i]>>p;
        if( st <= dr && d[st] == i - t ){
            st++;
        }
        while( st <= dr && c[i] <= c[d[dr]] + s * ( i - d[dr]) ){
            dr--;
        }
        d[++dr] = i;
        sum += p * ( c[d[st]] + s * ( i - d[st] ) );
    }
    out<<sum;
    return 0;
}