Cod sursa(job #2942311)

Utilizator RZV_BestBirsan Razvan RZV_Best Data 19 noiembrie 2022 15:48:12
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
int n,t,s,c[100005],p[100005],i;
long long x;
deque <int> d;
int main() {
  f>>n>>t>>s;
  for(i=1;i<=n;i++)
    f>>p[i]>>c[i];
  for(i=1;i<=n;i++)
    {
      if(!d.empty()&&d.front()==i-s-1)
        d.pop_front();
      while(!d.empty()&&p[d.back()]+t*(i-d.back())>p[i])
        d.pop_back();
      d.push_back(i);
      x+=1LL * c[i]*(p[d.front()]+1LL * t *(i-d.front()));
    }
  g<<x;
  return 0;
}