Submission #797048

#	Time	Username	Problem	Language	Result	Execution time	Memory
797048		tlnk07	Volontiranje (COCI21_volontiranje)	C++17	0 / 110	32 ms	67540 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long n,m,i,a[1000001],b[1000001], p[1000001], maxi = 0, cnt = 0;
bool check[1000001];
stack<int> sta[100001];
void LIS(int n)
{
	for(i=1;i<=n;i++)
	{
		if(check[i])	continue;
		for(int j=i - 1;j>=1;j--)
		{
			if(check[j])	continue;
			else if(a[i]>a[j])
			{
				if(b[j] + 1 > b[i])
				{
					b[i] = b[j] + 1;
					p[i] = j;
				}
			}
		}
		maxi = max(maxi, b[i]);
	}
}
int main()
{
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i]; 
		b[i]=1;
		p[i] = 0;
	}
	LIS(n);
	for(int i = n; i >= 1; --i)
	{
		if(maxi == b[i])
		{
			++cnt;
			long long temp = i;
			check[i] = true;
			while(temp != 0)
			{
				sta[cnt].push(a[temp]);
				temp = p[temp];
				check[temp] = true;
			}
			for(int i = 1; i <= n; ++i)
			{
				b[i] = 1;
				p[i] = 0;
			}
			LIS(n);
		}
	}
	cout << cnt << " " << maxi << "\n";
	for(int i = 1; i <= cnt; ++i)
	{
		while(!sta[i].empty())
		{
			cout << sta[i].top() << " ";
			sta[i].pop();
		}
		cout << "\n";
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60