Submission #239329

#	Time	Username	Problem	Language	Result	Execution time	Memory
239329		MrRobot_28	Vođe (COCI17_vode)	C++17	120 / 120	523 ms	632 KiB

vode

#include <bits/stdc++.h>
using namespace std;

signed main()
{
	int n, m, k;
	cin >> n >> m >> k;
	vector <int> a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	vector <vector <int> > dp(2, vector <int> (m, 0));
	vector <vector <int> > up1(2, vector <int> (m, 1e9));
	vector <vector <int> > up2(2, vector <int> (m, 1e9));
	vector <int> ans(n);
	for(int i = m + n - 1; i >= 0; i--)
	{
		up1[i % 2][m - 1] = up2[i % 2][m - 1] = 1e9; 
		for(int j = m - 1; j >= 0; j--)
		{
			if(i == m + n - 1 || j == m - 1)
			{
				dp[i % 2][j] = 0;
			}
			else if(a[(i + 1) % n] == a[i % n])
			{
				if(up1[1 - i % 2][j + 1] <= j + k)
				{
					dp[i % 2][j] = 1;
				}
				else
				{
					dp[i % 2][j] = 0;
				}
			}
			else
			{
				if(up2[1 - i % 2][j + 1] <= j + k)
				{
					dp[i % 2][j] = 1;
				}
				else
				{
					dp[i % 2][j] = 0;
				}
			}
			if(dp[i % 2][j] == 0)
			{
				if(j != m - 1)
				{
					up1[i % 2][j] = up1[i % 2][j + 1];
				}
				up2[i % 2][j] = j;
			}
			else
			{
				if(j != m - 1)
				{
					up2[i % 2][j] = up2[i % 2][j + 1];
				}
				up1[i % 2][j] = j;
			}
		}
		if(i < n)
		{
			
		if(a[i] == 0)
		{
			if(dp[i % 2][0])
			{
				ans[i] = 0;
			}
			else
			{
				ans[i] = 1;
			}
		}
		else
		{
			if(dp[i % 2][0])
			{
				ans[i] = 1;
			}
			else
			{
				ans[i] = 0;
			}
		}
		}
	}
	for(int i = 0; i < n; i++)
	{
		cout << ans[i] << " ";
	}
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12