Pagini recente » Cod sursa (job #3229647) | Diferente pentru implica-te/arhiva-educationala intre reviziile 223 si 70 | Cod sursa (job #893730) | Cod sursa (job #689254) | Cod sursa (job #2909762)
#include <bits/stdc++.h>
using namespace std;
int n;
pair <int,int> A[100005];
int dp[100005];
inline bool cmp(pair<int,int> a,pair<int,int> b){
if(a.second > b.second)
return false;
if(a.second < b.second)
return true;
return a.first < b.first;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for(int i = 1;i <= n; ++i)
cin >> A[i].first >> A[i].second;
sort(A + 1 ,A + 1 + n ,cmp);
int j = 1;
for(int i = 1;i <= A[n].second; ++i){
dp[i] = dp[i-1];
while(i == A[j].second){
if(dp[A[j].first] + A[j].second - A[j].first > dp[i])
dp[i] = dp[A[j].first] + A[j].second - A[j].first;
++j;
}
}
cout << dp[A[n].second];
}