Pagini recente » Cod sursa (job #951619) | Cod sursa (job #1911028) | Cod sursa (job #3032879) | Cod sursa (job #812890) | Cod sursa (job #3255391)
#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;
}