Pagini recente » Cod sursa (job #196298) | Cod sursa (job #647867) | Cod sursa (job #3258603) | Cod sursa (job #1746815) | Cod sursa (job #2050027)
#include <bits/stdc++.h>
#define NMAX 100005
#define INF 0x3f3f3f3f
using namespace std;
ifstream fi("heavymetal.in"); void Input();
ofstream fo("heavymetal.out"); void Output();
struct dur
{
int start, end;
bool operator <(const dur &other) const {return end < other.end;}
};
dur bands[NMAX];
long long dp[NMAX];
int N;
int binarySearch(int val)
{
int step = INF;
int pos = 0;
while (step != 0)
{
if (pos + step <= N && bands[pos + step].end <= val)
{
pos += step;
}
step /= 2;
}
return pos;
}
int main()
{
Input();
sort(bands + 1, bands + N + 1);
dp[1] = bands[1].end - bands[1].start;
for (int i = 2; i <= N; ++i)
{
int before = binarySearch(bands[i].start);
dp[i] = max( (bands[i].end - bands[i].start) + dp[before], dp[i - 1]);
}
Output();
}
void Input()
{
fi>>N;
for (int i = 1; i <= N; ++i)
{
fi>>bands[i].start>>bands[i].end;
}
}
void Output()
{
fo<<dp[N];
}