Cod sursa(job #2049452)

Utilizator Andrei_RAndrei Roceanu Andrei_R Data 27 octombrie 2017 10:56:27
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[100000], d[100000];

int main()
{
    int n, k, t, p, i, x, st, dr;
    long long sum;
    f >> n >> t >> p;
    dr = -1;
    for ( i = st = sum = 0; i < n; i++ ) {
        f >> v[i] >> x;
        if ( st <= dr && d[st] == i-p ) {
            st++;
        }
        while ( st <= dr && v[d[dr]] + ( i - d[dr] ) * t >= v[i] ) {
            dr--;
        }
        d[++dr] = i;
        sum += (long long)x * (v[d[st]] + ( i - d[st] ) * t);
    }
    g << sum;
    f.close();
    g.close();
    return 0;
}