oj.uz

Submission #239328

# Submission time Handle Problem Language Result Execution time Memory
239328 2020-06-15T11:49:13 Z MrRobot_28 Vođe (COCI17_vode) C++17
96 / 120
 720 ms 524292 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(m + n, vector <int> (m, 0));
	vector <vector <int> > up1(m + n, vector <int> (m, 1e9));
	vector <vector <int> > up2(m + n, vector <int> (m, 1e9));
	for(int i = m + n - 1; i >= 0; i--)
	{
		for(int j = m - 1; j >= 0; j--)
		{
			if(i == m + n - 1 || j == m - 1)
			{
				dp[i][j] = 0;
			}
			else if(a[(i + 1) % n] == a[i % n])
			{
				if(up1[i + 1][j + 1] <= j + k)
				{
					dp[i][j] = 1;
				}
				else
				{
					dp[i][j] = 0;
				}
			}
			else
			{
				if(up2[i + 1][j + 1] <= j + k)
				{
					dp[i][j] = 1;
				}
				else
				{
					dp[i][j] = 0;
				}
			}
			if(dp[i][j] == 0)
			{
				if(j != m - 1)
				{
					up1[i][j] = up1[i][j + 1];
				}
				up2[i][j] = j;
			}
			else
			{
				if(j != m - 1)
				{
					up2[i][j] = up2[i][j + 1];
				}
				up1[i][j] = j;
			}
		}
	}
	for(int i = 0; i < n; i++)
	{
		if(a[i] == 0)
		{
			if(dp[i][0])
			{
				cout << 0 << " ";
			}
			else
			{
				cout << 1 << " ";
			}
		}
		else
		{
			if(dp[i][0])
			{
				cout << 1 << " ";
			}
			else
			{
				cout << 0 << " ";	
			}
		}
	}
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3968 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 8 ms 3200 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3328 KB Output is correct
2 Correct 10 ms 3584 KB Output is correct
3 Correct 10 ms 3584 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5376 KB Output is correct
2 Correct 12 ms 4864 KB Output is correct
3 Correct 11 ms 4096 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5248 KB Output is correct
2 Correct 15 ms 5504 KB Output is correct
3 Correct 4 ms 256 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 67576 KB Output is correct
2 Correct 116 ms 79584 KB Output is correct
3 Correct 720 ms 501792 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 180856 KB Output is correct
2 Correct 619 ms 426016 KB Output is correct
3 Correct 274 ms 176248 KB Output is correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 298 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 273 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -