Cod sursa(job #2586139)

Utilizator Albert_GAlbert G Albert_G Data 19 martie 2020 20:41:59
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <deque>


using namespace std;

const int N = 1e5+1;
int v[N];

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

auto main() -> int
{
    int n,s,t,c;
    long long suma=0;
    in>>n>>s>>t;
    t++;
    deque <int> deq;
    for(int i=0; i<n; i++)
    {
        in>>v[i]>>c;
        if(!deq.empty() && deq.back() == i - t)
            deq.pop_back();
        while(!deq.empty() && v[deq.front()] + (i-deq.front())*s >= v[i] )
            deq.pop_front();
        deq.push_front(i);

        suma+= c * (v[deq.back()] + (i-deq.back()) * s);

    }
    in.close();
    out<<suma;
    out.close();
    return 0;
}