Cod sursa(job #2941679)

Utilizator Andrei_C123Costea Andrei Ioan Andrei_C123 Data 18 noiembrie 2022 01:44:09
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

const int NMAX = 1e6;
int ans[NMAX + 1];

struct Formatii {
	int a, b;

}v[NMAX + 1];

bool cmp(Formatii x, Formatii y) {
	if (x.b > y.b)
	{
		return false;
	}
	if (x.a > y.a && x.b == y.b)
	{
		return false;
	}
	return true;
}

int main() {

	int n, k = 1;
	int max;
	fin >> n;

	for (int i = 1; i <= n; i++) {
		fin >> v[i].a >> v[i].b;
	}

	sort(v + 1, v + n + 1, cmp);

	max = v[n].b;

	for (int i = 1; i <= max; i++) {
		ans[i] = ans[i - 1];

		while (i == v[k].b) {
			int temp = ans[v[k].a] + v[k].b - v[k].a;
			if (ans[i] <= temp) {
				ans[i] = temp;
			}
			k++;
		}
	}

	fout << ans[v[n].b];

	return 0;
}