Cod sursa(job #2197484)

Utilizator baiatu.danielaBaiatu Bianca baiatu.daniela Data 22 aprilie 2018 12:30:27
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");
int n,c,maxi=0;
struct ceva
{
    int ora,bani;
} v[2008];
void citeste()
{
   fin>>n>>c;
   for(int i=1; i<=n; i++)
   {
       fin>>v[i].ora>>v[i].bani;
   }
}
int compara(ceva a, ceva b)
{
    return a.ora<b.ora;
}
int profit(int poz)
{
    int s=0,profitdr=0,profitcrt,profitst=0,profitfin;
    for(int i=poz+1;i<=n;i++)
    {
        if(v[i].bani>=v[poz].bani)
            s=s+v[poz].bani;
        profitcrt=s-(v[i].ora-v[poz].ora)*c;
        profitdr=max(profitdr,profitcrt);
    }
    s=0;
    for(int i=poz-1;i>=1;i--)
    {
        if(v[i].bani>=v[poz].bani)
            s=s+v[poz].bani;
        profitcrt=s-(v[poz].ora-v[i].ora)*c;
        profitst=max(profitst,profitcrt);
    }
    profitfin=v[poz].bani-c;
    if(profitdr>0) profitfin+=profitdr;
    if(profitst>0) profitfin+=profitst;
    return profitfin;
}
int main ()
{
    citeste();
    sort(v+1,v+n+1,compara);
//    for(int i=1;i<=n;i++)
//        cout<<v[i].ora<<" "<<v[i].bani<<'\n';
 for(int i=1;i<=n;i++)
{
    maxi=max(profit(i),maxi);
}
fout<<maxi;

    return 0;
}