Cod sursa(job #2332966)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 31 ianuarie 2019 15:30:06
Problema Carnati Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <climits>
#include <algorithm>

#define NMAX 2005
using namespace std;

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

int dp;

struct chestie{
    int ind, val;
}v[NMAX];

inline bool cmp(chestie a, chestie b){
    return a.ind < b.ind;
}

int main()
{
    int n, c;
    fin >> n >> c;

    for(int i = 1; i <= n; ++i)
        fin >> v[i].ind >> v[i].val;

    sort(v + 1, v + n + 1, cmp);

    int maxxProf = INT_MIN;
    for(int i = 1; i <= n; ++i)
    {
        int poz = 1;
        while(poz <= n)
        {
            if(poz == 1)
                dp = (v[i].val <= v[1].val ? v[i].val : 0) - c;
            else
            {
                int x = (v[i].val <= v[poz].val ? v[i].val : 0) - c * (v[poz].ind - v[poz - 1].ind);
                if(dp + x > (v[i].val <= v[poz].val ? v[i].val : 0) - c)
                    dp += x;
                else
                    dp = (v[i].val <= v[poz].val ? v[i].val : 0) - c;
            }
            ++poz;
            maxxProf = max(maxxProf, dp);
        }
    }

    fout << maxxProf << '\n';
    return 0;
}