oj.uz

Submission #239329

# Submission time Handle Problem Language Result Execution time Memory
239329 2020-06-15T11:53:39 Z MrRobot_28 Vođe (COCI17_vode) C++17
120 / 120
 523 ms 632 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 7 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 384 KB Output is correct
2 Correct 77 ms 504 KB Output is correct
3 Correct 463 ms 632 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 384 KB Output is correct
2 Correct 391 ms 520 KB Output is correct
3 Correct 163 ms 384 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 528 KB Output is correct
2 Correct 276 ms 384 KB Output is correct
3 Correct 290 ms 504 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 632 KB Output is correct
2 Correct 429 ms 632 KB Output is correct
3 Correct 499 ms 632 KB Output is correct