oj.uz

Submission #827077

# Submission time Handle Problem Language Result Execution time Memory
827077 2023-08-16T08:35:33 Z Alora Selotejp (COCI20_selotejp) C++17
35 / 110
 1 ms 596 KB 
#include <bits/stdc++.h>
#define name "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define pb push_back
#define all(v) v.begin(), v.end()
#define maxn 255
const int M = 1e9 + 7;
using namespace std;
int m, n, full, pre[1 << 10], dp[1 << 10];
char s[maxn][maxn];

void sol(){
    full = (1 << m) - 1;
    memset(pre, 0x3f, sizeof(pre));
    pre[0] = 0;
    fi(j, 0, n - 1){
        fi(i, 0, m - 1){
            fi(tt, 0, full){
                // if i-th bit of tt = 0 -> cell(j, i) is shut by a horizontal tape
                // if i-th bit of tt = 1 -> cell(j, i) is shut by a vertical tape
                if(s[j][i] == '.'){
                    if(getbit(tt, i)) dp[tt] = 1e9;
                    else dp[tt] = min(pre[tt], pre[tt^(1 << i)]);
                    continue;
                }
                if(getbit(tt, i)) dp[tt] = min(pre[tt], pre[tt^(1 << i)] + 1);
                else{
                    dp[tt] = min(pre[tt], pre[tt^(1 << i)]);
                    if(i == 0 || s[j][i - 1] == '.' || getbit(tt, i - 1)) dp[tt]++;
                }
            }
            swap(pre, dp);
        }
    }
    int res = 1e9;
    fi(tt, 0, full) res = min(res, pre[tt]);
    cout << res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	//freopen(name".in","r",stdin);
	//freopen(name".out","w",stdout);
    cin >> n >> m;
    fi(i, 0, n - 1)
        fi(j, 0, m - 1) cin >> s[i][j];
    sol();
	return 0;
}

Compilation message

Main.cpp: In function 'void sol()':
Main.cpp:35:69: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   35 |                     if(i == 0 || s[j][i - 1] == '.' || getbit(tt, i - 1)) dp[tt]++;
      |                                                                   ~~^~~
Main.cpp:9:29: note: in definition of macro 'getbit'
    9 | #define getbit(i, j) ((i >> j) & 1)
      |                             ^

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 596 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 328 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 596 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -