Cod sursa(job #2203431)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 12 mai 2018 12:08:54
Problema Carnati Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 2001
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");

struct date
{
    int ora,bani;
}v[NMAX];
int N,c,answer;
int compara(const date &a, const date &b)
{
    return a.ora < b.ora;
}
int profit(int poz)
{
    int s=0,profitMax1=0,profitMax2=0,profitNet=0,profitTotal;
    for(int i = poz+ 1; i <= N; i++)
    {
        if(v[i].bani >= v[poz].bani)
              s+=v[poz].bani;
        profitNet=s-(v[i].ora - v[i-1].ora)*c;
        profitMax1=max(profitMax1,profitNet);
    }
    s=0,profitNet=0;
    for(int i= poz-1; i>=1; i--)
    {
        if(v[i].bani >= v[poz].bani)
            s+=v[poz].bani;
        profitNet=s-(v[i+1].ora-v[i].ora)*c;
        profitMax2=max(profitMax2,profitNet);
    }
    profitTotal=v[poz].bani-c;
    if(profitMax1 > 0 ) profitTotal+=profitMax1;
    if(profitMax2 > 0 ) profitTotal+=profitMax2;
    return profitTotal;
}
int main()
{
    fin>>N>>c;
    for(int i =1 ; i <= N; i++)
        fin>>v[i].ora>>v[i].bani;
        sort(v+1,v+N+1,compara);
    for(int i = 1; i <= N; i++)
    {
        answer=max(answer,profit(i));
    }
    fout<<answer;

    return 0;
}