Pagini recente » Cod sursa (job #1418497) | Cod sursa (job #2937916) | Cod sursa (job #136451) | Cod sursa (job #2803866) | Cod sursa (job #2218427)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
struct punk {
int st, dr;
}v[100002];
int dp[100002], n;
bool cmp (punk x, punk y) {
return x.dr < y.dr;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++){
fin >> v[i].st >> v[i].dr;
}
sort (v + 1, v + n + 1, cmp);
dp[1] = v[1].dr - v[1].st;
for (int i = 2; i <= n; i++) {
int st = 1, poz = 0, dr = i - 1;
while (st <= dr) {
int mij = (st + dr) / 2;
if (v[i].st >= v[mij].dr) {
st = mij + 1;
poz = mij;
}
else
dr = mij - 1;
}
dp[i] = max(dp[i - 1], dp[poz] + v[i].dr - v[i].st);
}
fout << dp[n];
return 0;
}