제출 #1184154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184154		nguyenkhangninh99	Selotejp (COCI20_selotejp)	C++20	110 / 110	12 ms	440 KiB

Main

#include <bits/stdc++.h>
using namespace std;
char mat[1005][15];

int main(){
	int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> mat[i][j];

    vector <int> dp(1 << m, 1e8), ndp(1 << m);
	dp[0] = 0;

	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
		for(int k = 0; k < (1 << m); k++) ndp[k] = (k & (1 << j) ? (mat[i][j] == '.' ? 1e8 : min(dp[k], dp[k ^ (1 << j)] + 1)) : min(dp[k], dp[k ^ (1 << j)]) + (mat[i][j] == '#' && (j == 0 || (k & (1 << (j - 1))) || mat[i][j - 1] == '.')));
		dp = ndp;
	}

   cout << *min_element(dp.begin(), dp.end()) << " ";
}

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