Cod sursa(job #2940613)

Utilizator nicuhasCemartan Nicolae nicuhas Data 15 noiembrie 2022 22:35:43
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX=2e3;
struct luc{
     long long poz,bani;
};
bool cmp(luc a,luc b){
    return a.poz<b.poz;
}
luc v[NMAX+1];
int main(){
    ifstream fin("carnati.in");
    ofstream fout("carnati.out");
    long long n,c,i,j,profit,bani,max1,st,max_prof=-99999999;
    fin>>n>>c;
    for(i=1;i<=n;i++){
        fin>>v[i].poz>>v[i].bani;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
        profit=0;
        max1=-99999999;
        st=1;
        for(j=1;j<=n;j++){
            if(v[j].bani>=v[i].bani){
                if(profit<(max(v[st].poz,v[j].poz)-min(v[st].poz,v[j].poz)+1)*c){
                    profit=0;
                    st=j;
                }
                profit+=v[i].bani;
            }
            max1=max(max1,profit-(max(v[st].poz,v[j].poz)-min(v[st].poz,v[j].poz)+1)*c);
        }
        max_prof=max(max_prof,max1);
    }
    fout<<max_prof;
    return 0;
}