Cod sursa(job #2972984)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 30 ianuarie 2023 19:19:11
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
/// Aceasta sursa este pentru problema
/// https://www.infoarena.ro/problema/branza
/// Punctaj: 100
/// Grupa Medie

#include<fstream>
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <vector>
#include <queue>
#include <iomanip>

#define DIM 100000
#define DIM2 10000000

using namespace std;

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

//ifstream f("in.in");
//ofstream g("out.out");

long long n,s,t,c[DIM2+5],p[DIM2+5],sol=0;

deque <long long> dq;

int main(){

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

        sol += p[i] * (c[dq.front()] + s*(i-dq.front()));
    }

    g<<sol;

    f.close();
    g.close();
    return 0;
}