Cod sursa(job #2062398)

Utilizator theblueninja10burea mihai ovidiu theblueninja10 Data 10 noiembrie 2017 12:26:35
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int c[100001], d[100001];

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

    return 0;
}