Cod sursa(job #2063880)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 11 noiembrie 2017 16:07:48
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXN 100000

using namespace std;

ifstream in("branza.in");
ofstream out("branza.out");

int n,t,s,c[MAXN],p[MAXN],d[MAXN];
long long int sum = 0;

void afis(){
    for(int i = 0 ; i < n; i ++)
        cerr<<d[i]<<" ";
    cerr<<endl;
}

int main()
{
    in>>n>>s>>t;
    for(int i = 0 ; i < n; i ++)
        in>>c[i]>>p[i];

    sum = 0;
    int st = 0,dr = -1;
    for(int i = 0 ; i < n; i ++){
        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[i]*(c[d[st]] + (long long)s*(i - d[st]));
    }
    out<<sum;

    return 0;
}