Submission #534313

#	Time	Username	Problem	Language	Result	Execution time	Memory
534313		maximath_1	Selotejp (COCI20_selotejp)	C++11	110 / 110	22 ms	368 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MX = 1005;
const int MXM = (1 << 10) + 5;
const int inf = 1e9 + 69;

int n, m;
string G[MX];
int dp[2][MXM]; 

bool bit(int msk, int tp){
	return ((msk >> tp) & 1);
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n >> m;
	for(int i = 0; i < n; i ++)
		cin >> G[i];

	int cr = 0;
	for(int i = 1; i < MXM; i ++)
		dp[cr][i] = inf;
	dp[cr][0] = 0;

	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++){
			for(int msk = 0; msk < (1 << m); msk ++){
				if(bit(msk, j) == 0){ // horizontal
					dp[cr ^ 1][msk] = min(dp[cr][msk], dp[cr][msk + (1 << j)]); //horizontal means above doesnt matter
					if(G[i][j] == '#' && (j == 0 || G[i][j - 1] == '.' || bit(msk, j - 1))) // if last square doesnt exist, new tape
						dp[cr ^ 1][msk] ++;
				}else{ // vertical
					if(G[i][j] == '.') dp[cr ^ 1][msk] = inf;
					else
						dp[cr ^ 1][msk] = min(dp[cr][msk], dp[cr][msk - (1 << j)] + 1); //compare with above current square is horizontal, new tape
				}
			}
			cr ^= 1;
		}
	}

	int ans = inf;
	for(int i = 0; i < (1 << m); i ++)
		ans = min(ans, dp[cr][i]);
	cout << ans << endl;
}

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