Cod sursa(job #1828350)

Utilizator borcanirobertBorcani Robert borcanirobert Data 13 decembrie 2016 09:44:10
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("carnati.in");
ofstream fout("carnati.out");

const int MAX = 2005;
struct Client{
    int t, p;

    bool operator < ( const Client& c ) const
    {
        return t < c.t;
    }
};
int N, C;
vector<Client> a;
int D[MAX];
int rez;

void Read();
void Solve();

int main()
{
    Read();
    Solve();

    fout << rez;

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int i, t, p;

    fin >> N >> C;
    for ( i = 1; i <= N; ++i )
    {
        fin >> t >> p;
        a.push_back({t, p});
    }

    sort( a.begin(), a.end() );
}

void Solve()
{
    int i, j, p, y;

    for ( const auto& x : a )
    {
        p = x.p;

        if ( p <= a[0].p )
            D[0] = a[0].p - C;
        else
            D[0] = 0;
        rez = max(rez, D[0]);
        for ( i = 1; i < N; ++i )
        {
            if ( p <= a[i].p )
                y = p;
            else
                y = 0;
            D[i] = max( D[i - 1] + y - C*(a[i].t - a[i - 1].t), y - C );
            rez = max( rez, D[i] );
        }
    }
}