Submission #637394

#	Time	Username	Problem	Language	Result	Execution time	Memory
637394		IWTIM	Selotejp (COCI20_selotejp)	C++17	110 / 110	277 ms	12192 KiB

Main

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 2000, inf = 1e9;
int t,n,m, dp[N][N],a[N][N], dphor[N],toadd[N];
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (int i = 1; i <= n; i++) {
    	for (int j = 0; j < m; j++) {
    		char ch;
    		cin>>ch;
    		a[i][j] = (ch == '#');
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < (1<<m); j++) {
			dp[i][j] = inf;
		}
	}
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		int all = 0;
		for (int x = 0; x < m; x++) {
			if (a[i][x]) all |= (1<<x);
		}
		for (int mask = 0; mask < (1<<m); mask++) {
			// Using only horizontal chains
			dphor[mask] = 0;
			if ((mask|all) != all) continue;
			for (int x = 0; x < m; x++) {
				if (mask&(1<<x)) {
					if (x == 0) {
						dphor[mask]++; continue;
					}
					if (mask&(1<<(x - 1))) continue;
					else  dphor[mask]++; 
				}
			}
		}
		for (int mask = 0; mask < (1<<m); mask++) toadd[mask] = inf;
		for (int mask = 0; mask < (1<<m); mask++) {
			// at least mask is used in the previous row
			for (int x = mask; x >= 0; x = (x - 1)&mask) {
				toadd[x] = min(toadd[x], dp[i - 1][mask]);
				if (x == 0) break;
			}
		}
		for (int mask = 0; mask < (1<<m); mask++) {
			dp[i][mask] = inf;
			// If a square is covered by a vertical chain ----- > mask[j] == 1
			// else mask[j] = 0;
			if ((mask | all) != all) continue;
			for (int x = mask; x >= 0; x = (x - 1) & mask) {
				dp[i][mask] = min(dp[i][mask], toadd[x] + __builtin_popcount(x ^ mask) + dphor[all ^ mask]);
				if (x == 0) break;
			}
		}
	}
	
	int ans = inf;
	for (int mask = 0; mask < (1<<m); mask++) ans = min(ans, dp[n][mask]);
	cout<<ans<<"\n";
}

Compilation message (stderr)

Main.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main() {
      | ^~~~

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