답안 #373307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373307	2021-03-04T04:33:39 Z	sam571128	Selotejp (COCI20_selotejp)	C++14	110 / 110	80 ms	80620 KB

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

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.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1004 KB	Output is correct
2	Correct	57 ms	74220 KB	Output is correct
3	Correct	20 ms	30060 KB	Output is correct
4	Correct	45 ms	70380 KB	Output is correct
5	Correct	61 ms	79372 KB	Output is correct
6	Correct	62 ms	79596 KB	Output is correct
7	Correct	61 ms	77548 KB	Output is correct
8	Correct	57 ms	74220 KB	Output is correct
9	Correct	58 ms	74604 KB	Output is correct
10	Correct	65 ms	80620 KB	Output is correct

Subtask #2

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1132 KB	Output is correct
2	Correct	1 ms	1132 KB	Output is correct
3	Correct	1 ms	1132 KB	Output is correct
4	Correct	1 ms	1132 KB	Output is correct
5	Correct	1 ms	1132 KB	Output is correct
6	Correct	2 ms	1268 KB	Output is correct
7	Correct	1 ms	620 KB	Output is correct
8	Correct	1 ms	1132 KB	Output is correct

Subtask #3

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1004 KB	Output is correct
2	Correct	57 ms	74220 KB	Output is correct
3	Correct	20 ms	30060 KB	Output is correct
4	Correct	45 ms	70380 KB	Output is correct
5	Correct	61 ms	79372 KB	Output is correct
6	Correct	62 ms	79596 KB	Output is correct
7	Correct	61 ms	77548 KB	Output is correct
8	Correct	57 ms	74220 KB	Output is correct
9	Correct	58 ms	74604 KB	Output is correct
10	Correct	65 ms	80620 KB	Output is correct
11	Correct	2 ms	1132 KB	Output is correct
12	Correct	1 ms	1132 KB	Output is correct
13	Correct	1 ms	1132 KB	Output is correct
14	Correct	1 ms	1132 KB	Output is correct
15	Correct	1 ms	1132 KB	Output is correct
16	Correct	2 ms	1268 KB	Output is correct
17	Correct	1 ms	620 KB	Output is correct
18	Correct	1 ms	1132 KB	Output is correct
19	Correct	11 ms	19948 KB	Output is correct
20	Correct	22 ms	32256 KB	Output is correct
21	Correct	48 ms	72556 KB	Output is correct
22	Correct	59 ms	78188 KB	Output is correct
23	Correct	60 ms	77548 KB	Output is correct
24	Correct	65 ms	77036 KB	Output is correct
25	Correct	63 ms	78956 KB	Output is correct
26	Correct	62 ms	75756 KB	Output is correct
27	Correct	64 ms	76012 KB	Output is correct
28	Correct	80 ms	78572 KB	Output is correct