Cod sursa(job #2586143)

Utilizator Albert_GAlbert G Albert_G Data 19 martie 2020 20:45:33
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 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+= (long long)c * (v[deq.back()] + (long long)(i-deq.back()) * s);

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