Cod sursa(job #2929341)

Utilizator raresgherasaRares Gherasa raresgherasa Data 25 octombrie 2022 17:24:44
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;

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

const int NM = 1e5 + 5;

int cost[NM], p[NM];
deque<int>dq;
int n, s, t, ans;

signed main(){
  fin >> n >> s >> t;
  for (int i = 1; i <= n; i++){
    fin >> cost[i] >> p[i];
    while (!dq.empty() && cost[i] <= cost[dq.back()] + s * (i - dq.back())){
      dq.pop_back();
    }
    while (!dq.empty() && i - dq.front() + 1 > t){
      dq.pop_front();
    }
    dq.push_back(i);
    ans += 1LL * p[i] * (cost[dq.front()] + s * (i - dq.front()));
  }
  fout << ans;
}