Cod sursa(job #2625949)

Utilizator toxic4ttoxic4t toxic4t Data 6 iunie 2020 11:05:17
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

long long c[100001], p[100001], deq[100001];
long long n, s, t, answ = 0, l = 0, r = -1;

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


    fin >> n >> s >> t;
    t++;

    for (int i = 0; i < n; i++)
        fin >> c[i] >> p[i];
    fin.close();

    for (int i = 0; i < n; i++){
        if (l <= r && deq[l] == (i-t))
            l++;
        while (l <= r && c[i] <= c[deq[r]] + (i-deq[r])*s)
            r--;
        deq[++r] = i;
        answ = answ + (c[deq[l]] + (i-deq[l])*s)*p[i];
}

    fout << answ;
    fout.close();
    return 0;
}