Submission #827080

#	Time	Username	Problem	Language	Result	Execution time	Memory
827080		Alora	Selotejp (COCI20_selotejp)	C++17	110 / 110	29 ms	356 KiB

Main

#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[1003][11];

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 (stderr)

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: 35 / 35
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40