Cod sursa(job #2049442)

Utilizator GhiciCineRazvan Dumitriu GhiciCine Data 27 octombrie 2017 10:33:52
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <cstdio>
#define MAXN 100000

using namespace std;

int v[MAXN + 5], d[MAXN + 5];
int main( ) {
  long long n, s, t,st, dr, sum, i, q;

  freopen( "branza.in", "r", stdin );
  freopen( "branza.out", "w", stdout );

  scanf( "%lld%lld%lld", &n, &s, &t );
  st = 0;
  dr = -1;
  sum = 0;
  t++;

  for( i = 0; i < n; i++ ) {
    scanf( "%d%lld", &v[i], &q );
    if( st <= dr && d[st] == i - t )
      st++;
    while( st <= dr && v[i] <= v[d[dr]] + ( i - d[dr] ) * s )
      dr--;
    d[++dr] = i;
    sum += (long long) ( v[d[st]] + (i - d[st]) * s ) * q;
  }
  printf( "%lld", sum );
  return 0;
}