Cod sursa(job #2065770)

Utilizator ilie0712Botosan Ilie ilie0712 Data 14 noiembrie 2017 10:26:03
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 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,S,T,p,i=0, dr, st;
    long long s=0;
    in>>N>>S>>T;
    T++;
    st=0;
    dr=-1;
    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;
        s += (c[d[st]] + (long long)S*(i-d[st]))*p;

    }
    out<<s;
    return 0;
}