Cod sursa(job #3264821)

Utilizator mateistefan11matei stefan mateistefan11 Data 24 decembrie 2024 13:00:36
Problema Heavy metal Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct act
{
    int x,y;
    long long z;
};
int n, urm[100005];
long long L[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,k;
    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;
}