Cod sursa(job #2678749)

Utilizator sebigeoGeorgescu Sebastian sebigeo Data 28 noiembrie 2020 16:21:45
Problema Carnati Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("carnati.in");
ofstream g("carnati.out");

int n,c;
struct mama
{
	int first,second;
}v[2000+10];

int solve(int indice)
{
    int suma=0;
    int rez=-10000000;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(v[indice].second<=v[i].second) cnt=v[indice].second;
        else cnt=0;
        suma=max(suma-(v[i].first-v[i-1].first)*c+cnt,cnt-c);
        if(suma<0)suma=0;
        rez=max(rez,suma);
    }
    return rez;
}
bool cmp(mama a,mama b)
{
    return a.first<b.first;
}

int main()
{
    int ans=-1000000;
    f >> n >> c;
    v[0].first=v[0].second=-10;
    for(int i=1; i<=n; i++)
    {
        f >> v[i].first >> v[i].second;

    }
    sort(v + 1,v + n+1,cmp);
    for(int j=1;j<=n;j++)
    {
        ans=max(ans,solve(j));
    }
    g<<ans;

    return 0;
}