Cod sursa(job #2344353)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 14 februarie 2019 23:55:46
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>

#define int_pair std::pair <int, int>

#define MAXN    2005
#define MAXP 1000005

int N, C, Ans;
int_pair V[MAXN];

std::ifstream In ("carnati.in");
std::ofstream Out("carnati.out");

void Citire() {
    In >> N >> C;
    for (int i=1; i<=N; ++i)
        In >> V[i].first >> V[i].second;
}

void Rezolvare() {
    std::sort(V+1, V+N+1);

    for (int i=1, j, DP; i<=N; ++i) {
        DP = 0;
        for (j=1; j<=N; ++j) {
            if (V[j].second < V[i].second)
                DP = DP - (V[j].first - V[j-1].first) * C;
            else {
                DP = DP + V[i].second - (V[j].first - V[j-1].first) * C;

                if (DP < V[i].second - C)
                    DP = V[i].second - C;
            }

            Ans = std::max(Ans, DP);
        }
    }   Out << Ans << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}