Cod sursa(job #1585785)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 31 ianuarie 2016 14:39:50
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;

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

const int dmax = 2000;
const int INF = 2000000005;

struct ELEMENT {int T, P;};
ELEMENT m[dmax + 1];

int d[dmax + 1]; // d[i] == PROFITUL MAXIM CE SE POATE OBTINE DACA MAGAZINUL ESTE DESCHIS LA TRECEREA CLIENTULUI i

int Max, answer = -INF;

int N, C;

bool exc(ELEMENT e1, ELEMENT e2)
{
    if(e1.T == e2.T) return e1.P < e2.P;
    else
        return e1.T < e2.T;
}

int main()
{
    int i, j;

    in >> N >> C;

    for(i = 1; i <= N; i++) in >> m[i].T >> m[i].P;

    sort(m + 1, m + N + 1, exc);

    m[0].T = m[1].T - 1;

    for(i = 1; i <= N; i++)
    {
        memset(d, 0, sizeof(d));
        Max = -INF;

        int x = m[i].P; //FIXEZ PRETUL

        for(j = 1; j <= N; j++)
        {
            if(m[j].P >= x) //CUMPAR PRODUSUL
                d[j] = max( d[j - 1] - (m[j].T - m[j - 1].T)*C + x, x - C);
            else
                d[j] = max(d[j - 1] - (m[j].T - m[j - 1].T)*C, -C);

            Max = max(Max, d[j]);
        }

        answer = max(answer, Max);
    }

    out << answer;

    return 0;
}