Pagini recente » Cod sursa (job #2288910) | Cod sursa (job #663303) | Cod sursa (job #42907) | Cod sursa (job #2266115) | Cod sursa (job #2973687)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");
/**
dp[t] = timpul maxim pe care il ascultam pana la secunda t
pentru concertul (l, r):
dp[l] = max(dp[l], dp[l-1])
dp[r] = max(dp[r], dp[l-1] + (r - l + 1)
**/
#define l a[i].first
#define r a[i].second
pair<int, int>a[100001];
int dp[200001];
vector<pair<int, int>>R[200001]; /// R[i] = care au capat in dreapta, {L, C} -> capatul din stanga de la segment, costul
int main()
{
int n;
in >> n;
vector<int>norm;
for (int i=1; i<=n; i++)
{
in >> l >> r;
norm.push_back(l);
norm.push_back(r);
}
sort(norm.begin(), norm.end());
for (int i=1; i<=n; i++)
{
int c = r - l;
l = lower_bound(norm.begin(), norm.end(), l) - norm.begin() + 1;
r = lower_bound(norm.begin(), norm.end(), r) - norm.begin() + 1;
R[r].push_back({l, c});
}
int m = (n << 1);
for (int rt=1; rt<=m; rt++)
{
dp[rt] = max(dp[rt], dp[rt-1]);
for (pair<int, int> pr : R[rt])
{
int lt = pr.first;
int C = pr.second;
dp[rt] = max(dp[rt], dp[lt] + C);
}
}
out << dp[m];
return 0;
}