97002024-03-01 12:03:44GervidHadjáratcpp17Időlimit túllépés 0/100300ms5252 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n, i, j;
    cin >> n;

	vector<pair<pair<int, int>, int>> a(n);
	for (i = 0; i < n; i++)
	{
		cin >> a[i].first.first >> a[i].first.second;
		a[i].second = i;
	}

	sort(a.begin(), a.end());

	vector<int> opt(n);
	opt[0] = 1;

	vector<int> last(n, -1);

	for (i = 1; i < n; i++)
	{
		int best = 0;
		for (j = i-1; j >= 0; j--)
		{
			if (a[j].first.second < a[i].first.second && opt[j] > best)
			{
				best = opt[j];
				last[i] = j;
			}
		}

		opt[i] = best + 1;
	}

	int max = 0, maxi;
	for (i = 0; i < n; i++)
	{
		if (opt[i] > max)
		{
			max = opt[i];
			maxi = i;
		}
	}

	cout << max << '\n';

	i = maxi;
	vector<int> out;
	out.reserve(max);

	while (i != -1)
	{
		out.push_back(i);
		i = last[i];
	}

	for (i = max-1; i >= 0; i--)
	{
		cout << a[out[i]].second + 1 << ' ';
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/100
1Elfogadva0/03ms1956 KiB
2Időlimit túllépés0/0300ms2428 KiB
3Hibás válasz0/43ms2320 KiB
4Hibás válasz0/43ms2404 KiB
5Hibás válasz0/43ms2468 KiB
6Hibás válasz0/42ms2576 KiB
7Hibás válasz0/43ms2820 KiB
8Hibás válasz0/43ms2920 KiB
9Hibás válasz0/43ms2976 KiB
10Hibás válasz0/46ms3120 KiB
11Hibás válasz0/465ms3536 KiB
12Időlimit túllépés0/4246ms4120 KiB
13Időlimit túllépés0/6246ms4120 KiB
14Időlimit túllépés0/6254ms3584 KiB
15Időlimit túllépés0/6261ms3884 KiB
16Időlimit túllépés0/6266ms4464 KiB
17Időlimit túllépés0/6273ms4580 KiB
18Időlimit túllépés0/6257ms4796 KiB
19Időlimit túllépés0/6266ms4952 KiB
20Időlimit túllépés0/6261ms5132 KiB
21Időlimit túllépés0/6286ms5252 KiB
22Időlimit túllépés0/6266ms5212 KiB