Pagini recente » Cod sursa (job #1248562) | Cod sursa (job #2697752) | Cod sursa (job #1767088) | Cod sursa (job #2908554) | Cod sursa (job #767880)
Cod sursa(job #767880)
#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];
int dp[100005];
inline int cmp (cutzu a, cutzu b) {
//if (a.f == b.f) return a.s < b.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 i, step;
for (step = 1; step < N; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < N && v[i + step].f <= val) i += step;
return i;
}
void Business () {
dp[0] = v[0].f - v[0].s;
int a, j;
for (int i = 1; i < N; i++)
{
a = B_Search (v[i].s);
for (j = a; v[j].f <= v[i].s; j++);
a = v[i].f - v[i].s + dp[j - 1];
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;
}