Cod sursa(job #3331604)

Utilizator sevescu_andreisevescu andrei sevescu_andrei Data 29 decembrie 2025 13:10:14
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <bits/stdc++.h>

using namespace std;

long long c[100005],p[100005];
deque <long long> 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-1)
            dq.pop_front();
        sum+=p[i]*(c[dq.front()]+s*(i-dq.front()));
    }
    fout << sum << endl;
    return 0;
}