Cod sursa(job #2049381)

Utilizator cip_ionescuCiprian Ionescu cip_ionescu Data 27 octombrie 2017 09:23:59
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#define MAX_N 100000

int v[MAX_N], d[MAX_N];

using namespace std;

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

int main()
{
    int n, s, t, st, dr, cant;
    long long S;

    fin >> n >> s >> t;
    t++;

    st = 0;
    dr = -1;
    S = 0;

    for(int i = 0 ; i < n ; i++){
        fin >> v[i] >> cant;

        if(st <= dr && d[st] == i - t) st++;

        while(st <= dr && v[i] <= v[d[dr]] + (i - d[dr]) * s) dr--;

        d[++dr] = i;
        S += (long long)(v[d[st]] + (i - d[st]) * (long long)s) * (long long)cant;
    }
    fout << S;
    return 0;
}