Cod sursa(job #3121286)

Utilizator mateionilaMatei Onila mateionila Data 11 aprilie 2023 17:52:07
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>
#define N 100005
#define mod 666013
using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int n,dp[N];
struct concert {
    int st, dr;
}a[N];

bool cmp(concert A, concert B)
{
    if (A.dr > B.dr) return 0;
    if (A.dr < B.dr) return 1;
    if (A.st < B.st) return 1;
    return 0;
}

int Caut(int x)
{
    int st = 1, dr = n, mij;
    int k=0;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (a[mij].dr <= x)
        {
            k = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    return k;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i].st >> a[i].dr;
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        int j = Caut(a[i].st);
        dp[i] = max(dp[i - 1], dp[j] + (a[i].dr - a[i].st));
    }
    fout << dp[n];
    return 0;
}