Cod sursa(job #2323353)

Utilizator mircearoataMircea Roata Palade mircearoata Data 19 ianuarie 2019 10:12:06
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>
#include <queue>

using namespace std;

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

int n, t, s;
long long sum;
int c[100001], p[100001];

deque<int> dq;

int main()
{
    in >> n >> s >> t;
    for(int i = 1; i <= n; i++)
    {
        in >> c[i] >> p[i];
        while(!dq.empty() && c[dq.front()]+s*(i-dq.front()) >= c[i])
            dq.pop_back();
        dq.push_back(i);
        if(dq.front() < i-t)
            dq.pop_front();
        sum += (c[dq.front()]+s*(i-dq.front()))*p[i];
    }
    out << sum;
    return 0;
}