Pagini recente » Cod sursa (job #1978377) | Cod sursa (job #42522) | Cod sursa (job #613516) | Cod sursa (job #2665795) | Cod sursa (job #767873)
Cod sursa(job #767873)
#include <fstream>
#include <algorithm>
using namespace std;
#define max(a, b) (a > b ? a : b)
typedef struct {
int s;
int f;
} cutzu;
int N;
cutzu v[100005];
long long dp[100005];
inline int cmp (cutzu a, cutzu b) {
if (a.f == b.f) return b.s < a.s;
return a.f < b.f;
}
void Citire () {
ifstream fin ("heavymetal.in");
fin >> N;
for (int i = 0; i < N; i++)
fin >> v[i].s >> v[i].f;
fin.close ();
sort (v, v + N, cmp);
}
int B_Search (int val, int ind) {
int i, step;
for (step = 1; step < ind; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < ind && v[i + step].f <= val) i += step;
return i;
}
void Business () {
dp[0] = 1LL * v[0].f - v[0].s;
long long a;
for (int i = 1; i < N; i++)
{
a = 1LL * v[i].f - v[i].s + dp[B_Search (v[i].s, i)];
dp[i] = max (dp[i - 1], a);
}
}
void Scriere () {
ofstream fout ("heavymetal.out");
fout << dp[N - 1];
fout.close ();
}
int main () {
Citire ();
Business ();
Scriere ();
return 0;
}