Cod sursa(job #3307873)

Utilizator InformaticianInDevenire1Munteanu Mihnea Gabriel InformaticianInDevenire1 Data 23 august 2025 10:45:52
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

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

int c[100005],p[100005];
int v[100005];
deque <pair <int,int>> dq;

signed main()
{
    int n,S,T;
    fin >> n >> S >> T;
    for (int i=1;i<=n;++i){
        fin >> c[i] >> p[i];
    }
    for (int j=1;j<=n;++j){
        v[j] = c[j]-S*j;
    }
    int ans = 0;
    for (int i=1;i<=n;++i){
        //int x = v[i];
        while (!dq.empty() and dq.back().first>v[i]) dq.pop_back();
        while (!dq.empty() and dq.front().second<i-T+1) dq.pop_front();
        dq.push_back({v[i],i});
        ans += (dq.front().first+S*i)*p[i];
    }
    fout << ans;
    return 0;
}