Cod sursa(job #2490959)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 11 noiembrie 2019 15:32:36
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.53 kb
#include <fstream>
#define N 100001
using namespace std;
long long v[N], q[N];
int main()
{
    ifstream fin("branza.in");
    ofstream fout("branza.out");
    long long n, i, s, k, st = 1, dr = 0, t, ss = 0;
    fin  >> n >> s >> k;
    for( i = 1; i <= n; i++ ){
        fin >> v[i] >> t;
        while(v[i] <= v[q[dr]] + ( i - q[dr] ) * s && st <= dr )
            dr--;
        dr++;
        q[dr] = i;
        if( q[st] + k < i )
            st++;
        ss += v[q[st]] * t + s * ( i- q[st] ) * t;
    }
    fout << ss;
    return 0;
}