Cod sursa(job #894313)

Utilizator SebiDDanila Sebastian SebiD Data 26 februarie 2013 20:39:35
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

const char infile[] = "carnati.in";
const char outfile[] = "carnati.out";

#define MAXN 2001

int N, C;

struct Carnat
{
    int T;
    int P;
};

Carnat A[MAXN];


int Result = 0;


int cmp(const Carnat a, const Carnat b)
{
    return a.T < b.T;
}


void citire()
{

    fstream fin(infile, ios::in);

    fin >> N >> C;

    for(int i = 0; i < N; i++)
    {
        fin >> A[i].T;
        fin >> A[i].P;

    }


    fin.close();

    sort(A, A+N, cmp);
}


int pd(int price)
{
    int best = 0;
    int profit = 0;
    int last = -1;
    for(int i = 0; i < N; i++)
    {
        if(A[i].P < price)
            continue;

        int max1 = profit + price - (A[i].T - last) * C;
        int max2 = price - C;

        profit = max(max1, max2);

        last = A[i].T;

        if(best < profit)
        {
            best = profit;
        }
    }
    return best;
}


void solve()
{
    for(int i = 0; i < N; i++)
    {
        Result = max(Result, pd(A[i].P));
    }
}


void afisare()
{
    fstream fout(outfile, ios::out);
    fout << Result << "\n";
    fout.close();
}

int main()
{
    citire();
    solve();
    afisare();
}