Cod sursa(job #2928061)

Utilizator LukyenDracea Lucian Lukyen Data 22 octombrie 2022 06:36:06
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;

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

int main()
{
  cin.rdbuf(fin.rdbuf());
  cout.rdbuf(fout.rdbuf());

  int n, k;
  cin >> n >> k;

  vector<pair<int, int>> vec(n + 1);
  for (int i = 1; i <= n; i++)
  {
    int x1, x2;
    cin >> x1 >> x2;
    vec[i] = make_pair(x1, x2);
  }

  sort(vec.begin() + 1, vec.end());

  int maxFin = INT_MIN;
  for (int i = 1; i <= n; i++)
  {
    int maxPrice = vec[i].second;

    int curr = 0, best = INT_MIN;
    for (int j = 1; j <= n; j++)
    {
      curr = curr - (vec[j].first - vec[j - 1].first) * k;

      if (curr < 0)
        curr = 0;

      if (vec[j].second >= maxPrice)
        curr += maxPrice;

      if (curr > best)
        best = curr - k;
    }
    if (best > maxFin)
      maxFin = best;
  }

  cout << maxFin;

  return 0;
}