제출 #852133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852133		Faee	Selotejp (COCI20_selotejp)	C++14	110 / 110	136 ms	195668 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second

const ll N = 1005;
const ll M = 10;
const ll INF = 1e9;

ll n,m;
char grid[N][M+2];
ll memo[N][M+2][(1 << M)+5][2];

ll dp(ll x, ll y, ll mask, ll stat) {
	if(x == n+1) return 0;
	ll temp = memo[x][y][mask][stat];
	if(temp != -1) return temp;
	temp = INF;
	if(y == m+1) temp = dp(x+1,1,mask,0);
	else {
		if(mask >> (y-1) & 1) {
			if(grid[x][y] == '.') {
				temp = min(temp,dp(x,y+1,mask-(1 << (y-1)),0));
			}
			else {
				temp = min({temp,dp(x,y+1,mask,0), dp(x,y+1,mask-(1 << (y-1)),1) + (stat^1)});
			}
		}
		else {
			if(grid[x][y] == '.') {
				temp = min(temp,dp(x,y+1,mask,0));
			}
			else {
				temp = min({temp,dp(x,y+1,mask + (1 << (y-1)),0)+1, dp(x,y+1,mask,1)+(stat^1)});
			}
		}
	}
	memo[x][y][mask][stat] = temp; 
	return memo[x][y][mask][stat];
}

int main() {
	memset(memo,-1,sizeof(memo));
	cin >> n >> m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin >> grid[i][j];
		}
	}
	cout << dp(1,1,0,0) << endl;
}

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