Cod sursa(job #3255391)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 10 noiembrie 2024 15:47:40
Problema Orase Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>

using namespace std;
const int NMAX = 50002;

ifstream cin("orase.in");
ofstream cout("orase.out");

struct casa {
    int ind, cat;
    bool operator <(const casa & rhs) const {
        if(ind != rhs.ind)
            return ind < rhs.ind;
        return cat < rhs.cat;
    }
}v[NMAX];
int dp[NMAX]; ///cel mai departat drum din spate(INCLUSIV i)
int main()
{
    int m, n;
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i].ind >> v[i].cat;
    sort(v + 1, v + n + 1);

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ///dist veche + adaugam dif de drum si add-ul nou de la v
        int dist = v[i].ind - v[i - 1].ind;
        ans = max(ans, dp[i - 1] + dist + v[i].cat);
        dp[i] = max(dp[i - 1] + dist, v[i].cat); ///suma celui mai dep drum INCLUSIV i
    }
    cout << ans;
    return 0;
}