Pagini recente » Cod sursa (job #80106) | Cod sursa (job #1551722) | Cod sursa (job #1283833) | Cod sursa (job #189792) | Cod sursa (job #3185098)
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int nmax = 2e5+5;
int dp[2*nmax];
struct Event{
int l,r,val;
bool operator < (const Event &other)
{
return r < other.r;
}
};
signed main()
{
int n; fin>>n;
vector<Event> v(n,{0,0,0});
map<int,int> norm;
for(int i=0; i<n; i++)
{
fin>>v[i].l>>v[i].r;
v[i].val = v[i].r - v[i].l;
v[i].r --;
norm[v[i].l] = 1;
norm[v[i].r] = 1;
}
int cnt = 1;
for(auto p: norm)
{
norm[p.first] = cnt++;
}
for(int i=0; i<n; i++)
v[i] = {norm[v[i].l],norm[v[i].r],v[i].val};
sort(v.begin(),v.end());
int i=0;
for(int timp = 1; timp <= 2*n; timp++)
{
dp[timp] = dp[timp-1];
while(v[i].r < timp)
{
i++;
}
while(v[i].r == timp)
{
dp[timp] = max(dp[timp],dp[v[i].l-1] + v[i].val);
i++;
}
}
fout<<dp[2*n];
return 0;
}