Submission #1184152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184152		nguyenkhangninh99	Selotejp (COCI20_selotejp)	C++20	110 / 110	12 ms	328 KiB

Main

#include <bits/stdc++.h>

using namespace std;
 
#define int long long

const int inf = 1e10;

char mat[1005][15];

void solve(){
    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, inf), novi(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++){
				if(k & (1 << j)) {
					if(mat[i][j] == '.') novi[k] = inf;
					else novi[k] = min(dp[k], dp[k ^ (1 << j)] + 1);
				}
				else {
					novi[k] = min(dp[k], dp[k ^ (1 << j)]);
					if(mat[i][j] == '#' && (j == 0 || (k & (1 << (j - 1))) || mat[i][j - 1] == '.')) novi[k]++;
				}
			}
			dp = novi;
		}
	}

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

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	solve();
}

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