Cod sursa(job #3126885)

Utilizator victorstefan28Cucu Victor Stefan victorstefan28 Data 7 mai 2023 01:27:16
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

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

int main()
{
    deque<int> dq;
    vector<long long> c,p;
    int n, s, t;
    in>>n>>s>>t;
    c.resize(n+2);
    p.resize(n+2);
    for(int i = 1; i<=n; i++)
    {
        in>>p[i]>>c[i];
        while(!dq.empty() && i-dq.front()>t)
            dq.pop_front();
        while(!dq.empty() && (p[dq.back()] + s*(i-dq.back())) > p[i])
            dq.pop_back();
        dq.push_back(i);
        sm+= c[i] * p[dq.front()] + s*(i-dq.front())*c[i];
    }
    out<<sm;
    return 0;
}