Pagini recente » Atasamentele paginii Profil root | Cod sursa (job #3362143) | Diferente pentru utilizator/root intre reviziile 1 si 3 | Istoria paginii utilizator/ftgryu | Cod sursa (job #3361705)
#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;
}