Cod sursa(job #2746899)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 28 aprilie 2021 17:45:38
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int MAXN = 1e5;
pair<int,int> a[MAXN];

void solve() {
  int N, S, T;
  fin >> N >> S >> T;
  deque<int> dq;
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    fin >> a[i].first >> a[i].second;
    while (!dq.empty() && a[i].first <= a[dq.back()].first + (i - dq.back()) * S)
      dq.pop_back();
    dq.emplace_back(i);
    while (i - dq.front() > T)
      dq.pop_front();
    ans += (a[dq.front()].first + (i - dq.front()) * S) * a[i].second;
  }
  fout << ans << '\n';
}

void close_files() {
  fin.close();
  fout.close();
}

int32_t main() {
  solve();
  close_files();
  return 0;
}