Submission #883588

#	Time	Username	Problem	Language	Result	Execution time	Memory
883588		TAhmed33	Selotejp (COCI20_selotejp)	C++98	110 / 110	132 ms	81500 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int dp[1000][10][1 << 10][2];
bool a[1000][10];
int n, m;
int checkbit (int mask, int x) {
	return (mask >> x) & 1;
}
int off (int mask, int x) {
	if (checkbit(mask, x)) mask ^= 1 << x;
	return mask;
}
int ans (int pos, int cur, int mask, int c) {
	if (pos == n) return 0;
	if (cur == m) {
		return ans(pos + 1, 0, mask, 0);
	}
	if (a[pos][cur] == 0) {
		return ans(pos, cur + 1, off(mask, cur), 0);
	}
	int &ret = dp[pos][cur][mask][c];
	if (ret != -1) return ret;
	ret = inf;
	if (checkbit(mask, cur)) {
		ret = min(ret, ans(pos, cur + 1, mask, 0));
	} else {
		ret = min(ret, 1 + ans(pos, cur + 1, mask ^ (1 << cur), 0));
	}
	if (c) {
		ret = min(ret, ans(pos, cur + 1, off(mask, cur), 1));
	} else {
		ret = min(ret, 1 + ans(pos, cur + 1, off(mask, cur), 1));
	}
	return ret;
}
int main () {
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			a[i][j] = c == '#';
		}
	}
	cout << ans(0, 0, 0, 0) << '\n';
}

• Subtask 1: 35 / 35
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40