Cod sursa(job #2938943)

Utilizator DumistefDumitrache Stefan Daniel Dumistef Data 12 noiembrie 2022 19:37:39
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("carnati.in");
   ofstream out("carnati.out");
struct c {
   int timp;
   int pret;
}v[2005];
bool sortare_timp(c a, c b) {
   return a.timp < b.timp;
}
int main() {
   long long n, rq, pretstabilit, profitcurent, sumcurent, profitmax, pretmax, st;
   in >> n >> rq;
   pretmax = 0;
   for (int i = 1; i <= n; i++)
      in >> v[i].timp >> v[i].pret;
   sort(v + 1, v + n + 1, sortare_timp);

   for (int i = 1; i <= n; i++) {
      pretstabilit = v[i].pret;
      sumcurent = 0;
      profitmax = -999999999;
      st = 0;
      for (int j = 1; j <= n; j++) {
         if (v[j].pret >= pretstabilit) {
            if (sumcurent < (v[j].timp - v[st].timp + 1) * rq) {
               sumcurent = 0;
               st = j;
            }
            sumcurent += pretstabilit;
         }
         profitcurent = sumcurent - (v[j].timp - v[st].timp + 1) * rq;
         profitmax = max(profitmax, profitcurent);
      }
      pretmax = max(pretmax, profitmax);
   }
   out << pretmax;
   return 0;
}