Cod sursa(job #2650334)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 18 septembrie 2020 14:12:56
Problema Carnati Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>
using namespace std;

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

struct guy{
  int t, p;
  friend operator<(guy x, guy y){
    return x.p>y.p;
  }
};

int n, c;
vector<guy> v;
int mint, maxt;
int t[2000];
int main()
{
  fin>>n>>c;
  v.resize(n+1);
  for(int i=1;i<=n;++i){
    fin>>v[i].t>>v[i].p;
    mint=min(mint, v[i].t);
    maxt=max(maxt, v[i].t);
  }
  sort(v.begin()+1, v.end());
  int ans=0;
  for(int i=1;i<=n;++i){
    int tmp=v[i].t, prc=v[i].p;
    t[tmp]++;
    int sol=t[tmp]*prc-c;
    int solr=0, r=0;
    for(int j=tmp+1;j<=maxt;++j){
      r+=t[j]*prc-c;
      solr=max(solr, r);
    }
    int soll=0, l=0;
    for(int j=tmp-1;j>=mint;--j){
      l+=t[j]*prc-c;
      soll=max(soll, l);
    }
    ans=max(ans, sol+soll+solr);
  }
  fout<<ans<<"\n";
  return 0;
}