oj.uz

Submission #401921

# Submission time Handle Problem Language Result Execution time Memory
401921 2021-05-11T01:58:43 Z idontreallyknow Vođe (COCI17_vode) C++17
120 / 120
 450 ms 96412 KB 
#include <bits/stdc++.h>
using namespace std;
const int mx = 5005;
int a[mx], suff[mx][mx];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,k;
	cin >> n >> m >> k;
	for (int q = 0; q < n; q++) cin >> a[q];
	for (int q = 0; q < n; q++) suff[q][m] = 1-a[q];
	for (int q = m-1; q >= 0; q--) {
		for (int w = 0; w < n; w++) {
			int e = w == n-1 ? 0 : w+1;
			int lo = q+1, hi = min(q+k,m);
			int z = suff[e][lo]-suff[e][hi+1];
			bool win = false;
			if (a[e] == 1 && z > 0) win = true;
			if (a[e] == 0 && z < hi-lo+1) win = true;
			int res = win ? a[e] : 1 - a[e];
			suff[w][q] = suff[w][q+1]+res;
		}
	}
	for (int q = 0; q < n; q++) {
		int w = q == 0 ? n-1 : q-1;
		cout << suff[w][0]-suff[w][1] << ' ';
	}
	cout << '\n';
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 460 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1996 KB Output is correct
2 Correct 3 ms 2380 KB Output is correct
3 Correct 3 ms 2252 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 2764 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2764 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 19140 KB Output is correct
2 Correct 55 ms 20692 KB Output is correct
3 Correct 409 ms 94796 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 38212 KB Output is correct
2 Correct 368 ms 94492 KB Output is correct
3 Correct 111 ms 41028 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 95336 KB Output is correct
2 Correct 4 ms 2508 KB Output is correct
3 Correct 2 ms 1504 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 95964 KB Output is correct
2 Correct 310 ms 96192 KB Output is correct
3 Correct 440 ms 96412 KB Output is correct