Submission #373307

#	Time	Username	Problem	Language	Result	Execution time	Memory
373307		sam571128	Selotejp (COCI20_selotejp)	C++14	110 / 110	80 ms	80620 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e3+5, M = 10;
int grid[N][M];
int dp[N][M][1<<M];

signed main(){
	fastio
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < m;j++){
			char c;
			cin >> c;
			if(c=='#') grid[i][j] = 1;
		}
	}
	for(int mask = 1;mask < (1<<m);mask++) dp[0][m-1][mask] = 1e18;
	for(int i = 1;i <= n;i++){
		for(int mask = 0; mask < (1<<m);mask++){
			if(grid[i][0]){
				if(mask&1) dp[i][0][mask] = min(dp[i-1][m-1][mask],dp[i-1][m-1][mask^1]+1);
				else dp[i][0][mask] = min(dp[i-1][m-1][mask],dp[i-1][m-1][mask^1])+1;
			}else{
				if(mask&1) dp[i][0][mask] = 1e18;
				else dp[i][0][mask] = min(dp[i-1][m-1][mask],dp[i-1][m-1][mask^1]);
			}
		}
		for(int j = 1;j < m;j++){
			for(int mask = 0; mask < (1<<m); mask++){
				if(grid[i][j]){
					if(mask&(1<<j)){
						dp[i][j][mask] = min(dp[i][j-1][mask],dp[i][j-1][mask^(1<<j)]+1);
					}else{
						if(grid[i][j-1]&&(mask&(1<<j-1))==0) dp[i][j][mask] = min(dp[i][j-1][mask],dp[i][j-1][mask^(1<<j)]);
						else dp[i][j][mask] = min(dp[i][j-1][mask],dp[i][j-1][mask^(1<<j)])+1;
					}
				}else{
					if(mask&(1<<j)) dp[i][j][mask] = 1e18;
					else dp[i][j][mask] = min(dp[i][j-1][mask],dp[i][j-1][mask^(1<<j)]);
				}
			}
		}
	}
	int ans = 1e18;
	for(int mask = 0; mask < (1<<m); mask++){
		ans = min(dp[n][m-1][mask],ans);
	}
	cout << ans << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |       if(grid[i][j-1]&&(mask&(1<<j-1))==0) dp[i][j][mask] = min(dp[i][j-1][mask],dp[i][j-1][mask^(1<<j)]);
      |                                  ~^~

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