oj.uz

Submission #314996

# Submission time Handle Problem Language Result Execution time Memory
314996 2020-10-21T21:56:46 Z FlashGamezzz Vođe (COCI17_vode) C++17
120 / 120
 871 ms 120560 KB 
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>

using namespace std;

int n, m, k, nt[5000][5001];
bool sg[5000], dp[5000][5000]; //n, m

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;

	for (int i = 0; i < n; i++){
		cin >> sg[i];
	}
	for (int i = 0; i < n; i++){
		dp[i][m-1] = !sg[i]; nt[i][m] = 0; nt[i][m-1] = !sg[i];
	}
	for (int i = m-2; i >= 0; i--){
		for (int j = 0; j < n; j++){
			int is = i+1, ie = min(m, i+k+1), il = ie-is, nv = (j+1) % n, itn = nt[nv][is]-nt[nv][ie];
			if (sg[j]){
				dp[j][i] = true;
				if (itn == 0){
					dp[j][i] = false;
				}
			} else {
				dp[j][i] = false;
				if (itn == il){
					dp[j][i] = true;
				}
			}
			nt[j][i] = nt[j][i+1]+dp[j][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 1 ms 384 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 768 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2464 KB Output is correct
2 Correct 2 ms 2304 KB Output is correct
3 Correct 3 ms 2560 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3456 KB Output is correct
2 Correct 3 ms 4096 KB Output is correct
3 Correct 3 ms 3840 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5132 KB Output is correct
2 Correct 4 ms 4864 KB Output is correct
3 Correct 4 ms 4480 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4480 KB Output is correct
2 Correct 5 ms 4736 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 27896 KB Output is correct
2 Correct 107 ms 29688 KB Output is correct
3 Correct 664 ms 118264 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 50524 KB Output is correct
2 Correct 636 ms 117888 KB Output is correct
3 Correct 229 ms 54780 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 119160 KB Output is correct
2 Correct 5 ms 3200 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 119928 KB Output is correct
2 Correct 648 ms 120300 KB Output is correct
3 Correct 871 ms 120560 KB Output is correct