Cod sursa(job #2490955)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 11 noiembrie 2019 15:27:41
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.51 kb
#include <fstream>
#define N 100001
using namespace std;
int v[N], q[N];
int main()
{
    ifstream fin("branza.in");
    ofstream fout("branza.out");
    int 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;
}