Cod sursa(job #2542339)

Utilizator PetyAlexandru Peticaru Pety Data 9 februarie 2020 20:19:21
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

#define f first
#define s second
#define pb push_back

ll n, s, t, c[100002], p[100002];
ll ans;
deque<ll>dq;

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