Cod sursa(job #2698391)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 21 ianuarie 2021 21:31:40
Problema Carnati Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
// Mihai Priboi

#include <bits/stdc++.h>

#define MAXN 2000

struct customer { int p, t; } v[MAXN];

int compar( const customer& a, const customer& b ) {
  return a.t < b.t;
}

int main() {
  FILE *fin, *fout;
  int n, c, i, j, price, profit, last_time, max, loss;
  fin = fopen( "carnati.in", "r" );

  fscanf( fin, "%d%d", &n, &c );
  for( i = 0; i < n; i++ )
    fscanf( fin, "%d%d", &v[i].t, &v[i].p );

  fclose( fin );

  // sortam dupa ora la care intra persoanele
  std::sort( v, v + n, compar );

  max = 0;
  // pentru fiecare pret posibil (pe care are sens sa il incercam) verificam profitul maxim (ssm)
  for( i = 0; i < n; i++ ) {
    price = v[i].p;

    // tratam separat primul numar pentru ca nu platim vanzatorul pana in primul moment (suntem zgarciti)
    profit = 0;
    if( v[0].p >= price )
      profit = price;

    max = std::max( profit - c, max );

    last_time = v[0].t;

    for( j = 1; j < n; j++ ) {
      loss = ( v[j].t - last_time ) * c;
      last_time = v[j].t;

      // >= ca sa nu platim vanzatorul mai mult decat e necesar (chiar daca nu schiba profitul)
      if( loss >= profit )
        profit = 0;
      else
        profit -= loss;

      if( v[j].p >= price )
        profit += price;

      // temporar, ora se completeaza doar daca e ultima
      profit -= c;
      max = std::max( profit, max );
      profit += c;
    }
  }

  fout = fopen( "carnati.out", "w" );
  fprintf( fout, "%d", max );
  fclose( fout );
  return 0;
}