9701 2024. 03. 01 12:10:29 Gervid Hadjárat cpp17 Időlimit túllépés 0/100 300ms 5268 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.first < a[i].first.first && 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 Összpont Teszt Verdikt Idő Memória
base 0/100
1 Elfogadva 0/0 3ms 1812 KiB
2 Időlimit túllépés 0/0 263ms 2300 KiB
3 Hibás válasz 0/4 3ms 2288 KiB
4 Hibás válasz 0/4 3ms 2500 KiB
5 Hibás válasz 0/4 3ms 2640 KiB
6 Hibás válasz 0/4 3ms 2856 KiB
7 Hibás válasz 0/4 3ms 3068 KiB
8 Hibás válasz 0/4 3ms 3200 KiB
9 Hibás válasz 0/4 3ms 3256 KiB
10 Hibás válasz 0/4 6ms 3272 KiB
11 Hibás válasz 0/4 68ms 3608 KiB
12 Időlimit túllépés 0/4 261ms 4048 KiB
13 Időlimit túllépés 0/6 259ms 4104 KiB
14 Időlimit túllépés 0/6 268ms 3284 KiB
15 Időlimit túllépés 0/6 273ms 3456 KiB
16 Időlimit túllépés 0/6 300ms 3912 KiB
17 Időlimit túllépés 0/6 268ms 4124 KiB
18 Időlimit túllépés 0/6 252ms 4236 KiB
19 Időlimit túllépés 0/6 273ms 4456 KiB
20 Időlimit túllépés 0/6 266ms 4888 KiB
21 Időlimit túllépés 0/6 259ms 5144 KiB
22 Időlimit túllépés 0/6 270ms 5268 KiB