Cod sursa(job #2926981)

Utilizator mihaistamatescuMihai Stamatescu mihaistamatescu Data 19 octombrie 2022 09:18:41
Problema Carnati Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <algorithm>
using namespace std;
struct client{
    int t, p;
}v[2010], x[2010];
bool cmp(client x, client y){
    if (x.t!=y.t){
        return x.t<y.t;
    }
    return x.p<y.p;
}
int n, c, pret, k, sol=-1e9;
int D[2010];
int main (){
    ifstream fin ("carnati.in");
    ofstream fout("carnati.out");
    fin>>n>>c;
    for (int i=1;i<=n;i++){
        fin>>v[i].t>>v[i].p;
    }
    sort(v+1, v+n+1, cmp);
    for (int i=1;i<=n;i++){
        int pret=v[i].p;
        k=0;
        for (int j=1;j<=n;j++){
            if (v[j].p>=pret){
                x[++k]=v[j];
            }
        }
        D[1]=pret-c;
        sol=max(sol, pret-c);
        for (int j=2;j<=k;j++){
            D[j]=max(D[j-1]+pret-(x[j].t-x[j-1].t)*c, pret-c);
            sol=max(D[j],sol);
        }
    }
    fout<<sol;
    return 0;
}