Mai intai trebuie sa te autentifici.
Cod sursa(job #3121286)
| Utilizator | 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;
}