Pagini recente » Cod sursa (job #1590987) | Monitorul de evaluare | Cod sursa (job #2017106) | Cod sursa (job #2482431) | Cod sursa (job #2055071)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, i, j, s, rez, mx, dp[100005];
int st, dr, mid, a, b;
struct metal
{ int in, sf, d; } v[100005];
bool comp(metal a, metal b)
{
if (a.in == b.in) return a.sf < b.sf;
return a.in < b.in;
}
int main () {
fin>>n;
for (i = 1; i <= n; i++)
{
fin >> v[i].in >> v[i].sf;
v[i].d = v[i].sf-v[i].in;
}
sort (v+1, v+n+1, comp);
mx = 0;
dp[1] = v[1].sf-v[1].in;
for (i = 2; i <= n; i++)
{
st = 1; dr = i-1;
while (st <= dr)
{
mid = st+(dr-st)/2;
if (v[mid].sf > v[i].in) dr = mid-1;
if (v[mid].sf <= v[i].in) st = mid+1;
}
if (v[mid+1].sf <= v[i].in) mid++;
if (v[mid].sf > v[i].in) mid--;
dp[i] = dp[mid]+(v[i].sf-v[i].in);
if (dp[i] < dp[i-1]) dp[i] = dp[i-1];
if (dp[i] > mx) mx = dp[i];
}
fout << mx << "\n";
}