Cod sursa(job #2732493)

Utilizator iustin.pericicaPericica Iustin iustin.pericica Data 28 martie 2021 23:32:11
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<stdio.h>
#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("branza.in");

ofstream fout("branza.out");

using namespace std;

long n,s,t,c[100002],p[100002];
long pozitie[100002],coada[100002];
long a, b;
long long solutie,x[100002];

int main(){
  fin>>n>>s>>t;
  a = 1; b = 0;
  for(int i = 1;i<=n;++i){
    fin>>c[i]>>p[i];
  }

  for(int i = 1;i<=n;++i){
    while(coada[b] + s * (i - pozitie[b]) > c[i] && a <= b){
        b-=1;
    }
    b++;
    coada[b] = c[i];
    pozitie[b] = i;

    while((i - pozitie[a]) > t && b > a)a++;

    x[i] = (long long)coada[a] + (long long)(i - pozitie[a])*s;


  }

  for(int i = 1;i<=n;++i){
    solutie+=(long long)(x[i] * p[i]);
  }

  fout<<solutie;

  return 0;
}