Submission #1288655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288655		euthymia2606	Selotejp (COCI20_selotejp)	C++20	110 / 110	35 ms	644 KiB

Main

#include <bits/stdc++.h> 

using namespace std;  

typedef long long ll;  
typedef pair<int, int> ii;  

const int INF = 1e9;  
const ll LINF = 1e18;  

template<typename T>
void minimize(T& a, const T& b) {
	if (b < a) a = b; 
}

const int N = 1e3 + 5;  

int n, m;  
string s[N]; 
int dp[2][11][1 << 10][2];

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); 	
	cin >> n >> m; 
	for (int i = 0; i < n; i++) cin >> s[i]; 

	for (int j = 0; j <= m; j++) {
		for (int mask = 0; mask < (1 << m); mask++) {
			for (int pre = 0; pre < 2; pre++) dp[0][j][mask][pre] = INF; 
		}
	}
	dp[0][0][0][0] = 0;  

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int mask = 0; mask < (1 << m); mask++) {
				for (int pre = 0; pre < 2; pre++) dp[(i + 1) & 1][j][mask][pre] = INF;  
			}
		}
		for (int j = 0; j <= m; j++) {
			for (int mask = 0; mask < (1 << m); mask++) {
				for (int pre = 0; pre < 2; pre++) {
					if (dp[i & 1][j][mask][pre] == INF) continue; 
					if (j == m) {
						minimize(dp[(i + 1) & 1][0][mask][0], dp[i & 1][j][mask][pre]); 
						continue;
					}
					if (s[i][j] == '.') {
						minimize(dp[i & 1][j + 1][mask & ~(1 << j)][0], dp[i & 1][j][mask][pre]);
						continue;
					}
					if ((mask >> j) & 1) {
						minimize(dp[i & 1][j + 1][mask][0], dp[i & 1][j][mask][pre]); 
						minimize(dp[i & 1][j + 1][mask ^ (1 << j)][0], dp[i & 1][j][mask][pre]);
					}
					else {
						if (pre == 1) {
							minimize(dp[i & 1][j + 1][mask][1], dp[i & 1][j][mask][pre]);
						}
						minimize(dp[i & 1][j + 1][mask][1], dp[i & 1][j][mask][pre] + 1);
						minimize(dp[i & 1][j + 1][mask | (1 << j)][0], dp[i & 1][j][mask][pre] + 1); 
					}
				}
			}
		}
	}

	int ans = INF;  
	for (int mask = 0; mask < (1 << m); mask++) {
		minimize(ans, dp[n & 1][0][mask][0]); 
	}

	cout << ans << '\n';
}

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