제출 #40393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40393		szawinis	Vođe (COCI17_vode)	C++14	120 / 120	2383 ms	97392 KiB

vode

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12