Cod sursa(job #1907054)

Utilizator osiaccrCristian Osiac osiaccr Data 6 martie 2017 17:36:39
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>

using namespace std;

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

int n, s, t, Front, Back, d[100001];
unsigned long long  v[100001][2], sum;


int main () {
    fin >> n >> s >> t;
    for (int i = 1; i <= n; i++)
        fin >> v[i][0] >> v[i][1];

    Front = 1;
    Back = 0;
    for (int i = 1; i <= n; i++) {
        while (Back >= Front && v[i][0] <= v[d[Back]][0] + (i - d[Back]) * s)
            Back--;

        d[++Back] = i;

        if (i - d[Front] >= t)
            Front--;

        sum += (v[d[Front]][0] + (i - d[Front]) * s) * v[i][1];

    }

    fout << sum;

    return 0;
}