oj.uz

Submission #852133

# Submission time Handle Problem Language Result Execution time Memory
852133 2023-09-21T09:44:34 Z Faee Selotejp (COCI20_selotejp) C++14
110 / 110
 136 ms 195668 KB 
#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.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 194640 KB Output is correct
2 Correct 26 ms 195416 KB Output is correct
3 Correct 26 ms 195356 KB Output is correct
4 Correct 25 ms 195280 KB Output is correct
5 Correct 28 ms 195668 KB Output is correct
6 Correct 29 ms 195668 KB Output is correct
7 Correct 29 ms 195420 KB Output is correct
8 Correct 23 ms 195408 KB Output is correct
9 Correct 27 ms 195524 KB Output is correct
10 Correct 55 ms 195416 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 194956 KB Output is correct
2 Correct 22 ms 194652 KB Output is correct
3 Correct 24 ms 194696 KB Output is correct
4 Correct 23 ms 194644 KB Output is correct
5 Correct 22 ms 194652 KB Output is correct
6 Correct 21 ms 194652 KB Output is correct
7 Correct 23 ms 194584 KB Output is correct
8 Correct 21 ms 194656 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 194640 KB Output is correct
2 Correct 26 ms 195416 KB Output is correct
3 Correct 26 ms 195356 KB Output is correct
4 Correct 25 ms 195280 KB Output is correct
5 Correct 28 ms 195668 KB Output is correct
6 Correct 29 ms 195668 KB Output is correct
7 Correct 29 ms 195420 KB Output is correct
8 Correct 23 ms 195408 KB Output is correct
9 Correct 27 ms 195524 KB Output is correct
10 Correct 55 ms 195416 KB Output is correct
11 Correct 24 ms 194956 KB Output is correct
12 Correct 22 ms 194652 KB Output is correct
13 Correct 24 ms 194696 KB Output is correct
14 Correct 23 ms 194644 KB Output is correct
15 Correct 22 ms 194652 KB Output is correct
16 Correct 21 ms 194652 KB Output is correct
17 Correct 23 ms 194584 KB Output is correct
18 Correct 21 ms 194656 KB Output is correct
19 Correct 23 ms 195000 KB Output is correct
20 Correct 29 ms 195616 KB Output is correct
21 Correct 30 ms 195416 KB Output is correct
22 Correct 23 ms 195420 KB Output is correct
23 Correct 23 ms 195340 KB Output is correct
24 Correct 25 ms 195356 KB Output is correct
25 Correct 36 ms 195460 KB Output is correct
26 Correct 65 ms 195520 KB Output is correct
27 Correct 102 ms 195524 KB Output is correct
28 Correct 136 ms 195548 KB Output is correct