Cod sursa(job #2053356)

Utilizator mirunaFmiruna mirunaF Data 31 octombrie 2017 18:15:03
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N=100001;
int n,s,t,c[N],p[N],v[N];
long long sum;

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