oj.uz

Submission #40393

# Submission time Handle Problem Language Result Execution time Memory
40393 2018-01-31T13:14:11 Z szawinis Vođe (COCI17_vode) C++14
120 / 120
 2383 ms 97392 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;

struct fenwick {
	int f[N];
	void update(int i, int v) { ++i; while(i < N) f[i] += v, i += i & -i; }
	int query(int i) {
		++i;
		int ret = 0;
		while(i > 0) ret += f[i], i -= i & -i;
		return ret;
	}
	int query(int l, int r) { return query(r) - query(l-1); }
};

int n, m, k;
bool state[N];
fenwick dp[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++) cin >> state[i];
	for(int j = m-1; j >= 1; j--) for(int i = n-1; i >= 0; i--) {
		if(state[(i+1) % n] == state[i])
			dp[i].update(j, dp[(i+1) % n].query(min(m, j+1), min(m, j+k)) > 0);
		else
			dp[i].update(j, dp[(i+1) % n].query(min(m, j+1), min(m, j+k)) == 0);
	}
	for(int i = 0; i < n; i++) {
		bool res = 0;
		for(int j = 1; j <= min(m-1, k); j++) res |= dp[i].query(j, j) == 1;
		cout << (res ^ 1 ^ state[i]) << ' ';
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5728 KB Output is correct
2 Correct 14 ms 6628 KB Output is correct
3 Correct 14 ms 6628 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7936 KB Output is correct
2 Correct 19 ms 7936 KB Output is correct
3 Correct 17 ms 7936 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7936 KB Output is correct
2 Correct 24 ms 7936 KB Output is correct
3 Correct 2 ms 7936 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 28860 KB Output is correct
2 Correct 288 ms 29260 KB Output is correct
3 Correct 1750 ms 95488 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 95488 KB Output is correct
2 Correct 1648 ms 95488 KB Output is correct
3 Correct 598 ms 95488 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1890 ms 96040 KB Output is correct
2 Correct 25 ms 96040 KB Output is correct
3 Correct 18 ms 96040 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1854 ms 96796 KB Output is correct
2 Correct 1623 ms 97044 KB Output is correct
3 Correct 2383 ms 97392 KB Output is correct