Cod sursa(job #3361705)

Utilizator SebimunMunteanu Sebastian Sebimun Data 27 iulie 2026 19:35:42
Problema Orase Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <cmath>
#include <fstream>
#include <algorithm>
using namespace std;

pair<int, int> v[50005];
int n, m, maxim, lung;
int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v+1, v+n+1); // sorteaza dupa first. daca first sunt egale, sorteaza dupa second
    // orasul i si orasul j, unde d[j] > d[i]

    // lungimea drumului: l[i] + (d[j] - d[i]) + l[j]
    int i = 1;
    for (int j = 2; j <= n; j ++) {
        //i = orasul din stanga lui j cel mai departat de j
        int lung = v[i].second + (v[j].first - v[i].first) + v[j].second;
        if (lung > maxim)
            maxim = lung;

        // l[j]   l[i]+(d[j]-d[i])
        if (v[j].second > v[i].second + (v[j].first - v[i].first)) {
            i = j; // j este mai departat decat i
        }
    }
    cout << maxim;

    return 0;
}