Cod sursa(job #2889597)

Utilizator Dimitri1999Dimitri-Theodor Mitran Dimitri1999 Data 12 aprilie 2022 23:13:07
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <iostream>
#include <fstream>
#define LEN 100005

using namespace std;

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

long long N, S, T, st, dr, sol;
long long c[LEN], p[LEN], d[LEN];

int main (){
     fin>>N>>S>>T;
     for(int i=1; i<=N; i++)
          fin>>c[i]>>p[i];


     d[1]=1, st=1, dr=1;

     sol+=c[1]*p[1];
     for(int i=2; i<=N; i++){

          while(st <= dr && c[i] <= c[d[dr]] + S*(i-d[dr]))
               dr--;
          d[++dr]=i;

          if(i-d[st] == T+1) st++;

          sol+=(c[d[st]] + S*(i-d[st])) * p[i];
     }

     fout<<sol;
     return 0;
}