Pagini recente » Cod sursa (job #945228) | Cod sursa (job #1850527) | Cod sursa (job #1945574) | probleme_de_oni-runda2019 | Cod sursa (job #3264819)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct act
{
int x,y,z;
};
int n, L[100005], urm[100005];
act a[10005];
/**
4
1 3 1
2 6 8
4 7 2
10 11 5
dp[1] = 1
dp[2] =
*/
bool cmp(act a, act b)
{
return a.y < b.y;
}
void afis(int p)
{
if(p == 0) return;
afis(urm[p]);
cout << a[p].x << " " << a[p].y << "\n";
}
int main()
{
int i,j;
fin >> n;
for(i = 1; i <= n; i++)
{
fin >> a[i].x >> a[i].y;
a[i].z = a[i].y - a[i].x;
}
sort(a + 1, a + n + 1, cmp);
for(i = 1; i <= n; i++)
{
k = -1;
L[i] = a[i].z;
for(j = 1; j < i; j++)
if(a[j].y <= a[i].x && L[i] < L[j] + a[i].z)
{
L[i] = L[j] + a[i].z;
urm[i] = j;
}
}
int mx = L[1], p = 1;
for(i = 2; i <= n; i++)
if(mx < L[i])
{
mx = L[i];
p = i;
}
fout << L[n];
return 0;
}