oj.uz

Submission #200192

# Submission time Handle Problem Language Result Execution time Memory
200192 2020-02-05T16:15:02 Z Saboon Vođe (COCI17_vode) C++14
120 / 120
 898 ms 106168 KB 
#include <iostream>

using namespace std;

const int maxn = 5e3 + 500;
int dp[maxn][maxn];
int num[2][maxn];
int ani[maxn];

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
		cin >> ani[i]; // 0 is a sheep, 1 is a goat
	for (int i = 0; i < n; i++){
		dp[i][m - 1] = (ani[i] ^ 1);
		num[ani[i] ^ 1][i] ++;
	}
	for (int j = m - 2; j >= 0; j--){
		for (int i = 0; i < n; i++){
			int nex = (i + 1) % n;
			if (num[ani[i]][nex])
				dp[i][j] = ani[i];
			else
				dp[i][j] = ani[i] ^ 1;
//			cout << i << " " << j << " " << dp[i][j] << endl;
		}
		for (int i = 0; i < n; i++){
			num[dp[i][j]][i] ++;
			if (j + k < m) 
				num[dp[i][j + k]][i] --;
		}
	}
	for (int i = 0; i < n; i++)
		cout << dp[i][0] << " ";
	
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2040 KB Output is correct
2 Correct 8 ms 2424 KB Output is correct
3 Correct 8 ms 2296 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3064 KB Output is correct
2 Correct 9 ms 2936 KB Output is correct
3 Correct 8 ms 2680 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2680 KB Output is correct
2 Correct 9 ms 2808 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 19192 KB Output is correct
2 Correct 124 ms 20728 KB Output is correct
3 Correct 791 ms 104312 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 38264 KB Output is correct
2 Correct 717 ms 96296 KB Output is correct
3 Correct 257 ms 41276 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 898 ms 104952 KB Output is correct
2 Correct 14 ms 2808 KB Output is correct
3 Correct 9 ms 1784 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 105708 KB Output is correct
2 Correct 686 ms 103416 KB Output is correct
3 Correct 737 ms 106168 KB Output is correct