Cod sursa(job #2213086)

Utilizator YeahICanVintila Valentin Ioan YeahICan Data 15 iunie 2018 16:55:28
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>
using namespace std;

const int N = 5000000;
int d[N], v[N], n, k;

int main()
{
    ifstream fin("branza.in");
    ofstream fout("branza.out");
    long long n, k, s, p, t; fin >> n >> s >> t; k = t;
    long long st = 0, dr = -1;
    long long S = 0;
    for(int i = 0; i < n; ++i)
    {
        fin >> v[i] >> p;
        /// scot din coada
        if(d[st] == i-k)
            ++st;
        /// scot din dreapta poz pe care nu voi avea minim
        while(st <= dr && v[i] <= v[d[dr]] + (i - d[dr])*s)
            --dr;
        d[++dr] = i;
        S += p * (v[d[st]] + (i - d[st])*s);
    }
    fout << S; return 0;
}