Cod sursa(job #3331590)

Utilizator sevescu_andreisevescu andrei sevescu_andrei Data 29 decembrie 2025 12:25:48
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>
#include <deque>

using namespace std;

long long c[100000],p[100000];
deque <int> dq;

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

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