Submission #1154098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154098		siewjh	Selotejp (COCI20_selotejp)	C++20	110 / 110	31 ms	44356 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
bool arr[1001][11];
int dp[1001][11][1024];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int rows, cols, p2c; cin >> rows >> cols;
	p2c = 1 << cols;
	for (int r = 1; r <= rows; r++){
		for (int c = 0; c < cols; c++){
			char ch; cin >> ch;
			arr[r][c] = (ch == '#');
		}
	}
	dp[0][cols - 1][0] = 0;
	for (int b = 1; b < p2c; b++) dp[0][cols - 1][b] = inf;
	int cm = 0;
	for (int r = 1; r <= rows; r++){
		for (int c = 0; c < cols; c++){
			if (arr[r][c] != arr[r - 1][c]) cm ^= (1 << c);
			for (int b = 0; b < p2c; b++){
				if ((cm | b) != cm) dp[r][c][b] = inf;
				else if (c == 0){
					if (b & (1 << c)) dp[r][c][b] = min(dp[r - 1][cols - 1][b], dp[r - 1][cols - 1][b ^ (1 << c)] + 1);
					else dp[r][c][b] = min(dp[r - 1][cols - 1][b], dp[r - 1][cols - 1][b ^ (1 << c)]) + arr[r][c];
				}
				else{
					if (b & (1 << c)) dp[r][c][b] = min(dp[r][c - 1][b], dp[r][c - 1][b ^ (1 << c)] + 1);
					else dp[r][c][b] = min(dp[r][c - 1][b], dp[r][c - 1][b ^ (1 << c)]) + (arr[r][c] && (!arr[r][c - 1] || (b & (1 << (c - 1)))));
				}
			}
		}
	}
	int ans = inf;
	for (int b = 0; b < p2c; b++) ans = min(ans, dp[rows][cols - 1][b]);
	cout << ans;
}

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