Cod sursa(job #2937238)

Utilizator deerMohanu Dominic deer Data 10 noiembrie 2022 09:09:47
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;
struct client {
   int timp;
   int pret;
}v[2005];
bool sort_timp(client a, client b) {
   return a.timp < b.timp;
}
int main() {
   ifstream cin("carnati.in");
   ofstream cout("carnati.out");
   long long n, c, pret_stabilit, profit_curent, sum_curent, profit_max, pmax, st;
   cin >> n >> c;
   pmax = 0;
   for (int i = 1; i <= n; i++)
      cin >> v[i].timp >> v[i].pret;
   sort(v + 1, v + n + 1, sort_timp);
   ///presupunem ca pretul stabilit de Gigel pentru un carnat este v[i], 1<=i<=n iar pentru fiecare element vom calcula profitul
   for (int i = 1; i <= n; i++) {
      pret_stabilit = v[i].pret;
      sum_curent = 0;
      profit_max = LLONG_MIN;
      st = 0;
      for (int j = 1; j <= n; j++) {
         if (v[j].pret >= pret_stabilit) {
            if (sum_curent < (v[j].timp - v[st].timp + 1) * c) { ///Gigel iese pe minus, asa ca incheiem subsecventa
               sum_curent = 0;
               st = j;
            }
            sum_curent += pret_stabilit;
         }
         profit_curent = sum_curent - (v[j].timp - v[st].timp + 1) * c;
         profit_max = max(profit_max, profit_curent);
      }
      pmax = max(pmax, profit_max);
   }
   cout << pmax;
   return 0;
}