제출 #1228591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228591		_callmelucian	Selotejp (COCI20_selotejp)	C++17	110 / 110	47 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int block[1010], dp[2][1 << 10], partial[1 << 10][11], n, m;

int cnt (int mask) {
    int cur = 0, ans = 0;
    for (int i = 0; i < n; i++, mask >>= 1) {
        if (mask & 1) ans += cur, cur = 0;
        else cur = 1;
    }
    return ans + cur;
}

bool getCur (int mask, int pos) {
    return mask >> pos & 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

//    int n, m; cin >> n >> m;
//    for (int i = 0; i < n; i++) {
//        for (int j = 1; j <= m; j++) {
//            char c; cin >> c;
//            if (c == '#') block[j] |= (1 << i);
//        }
//    }
//    block[0] = (1 << n) - 1;
    cin >> m >> n;
    for (int j = 1; j <= m; j++) {
        for (int i = 0; i < n; i++) {
            char c; cin >> c;
            if (c == '.') block[j] |= (1 << i);
        }
    }
    block[0] = (1 << n) - 1;

    fill(dp[0] + 1, dp[0] + (1 << n), INT_MAX);
    for (int j = 1; j <= m; j++) {
        int t = j & 1;
        for (int mask = 0; mask < (1 << n); mask++) {
            partial[mask][0] = dp[t ^ 1][mask];
            fill(partial[mask] + 1, partial[mask] + n + 1, INT_MAX);
        }
        for (int k = 1; k <= n; k++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                if (mask & block[j] & ((1 << k) - 1)) continue;
                if (!getCur(mask, k - 1))
                    partial[mask][k] = min(partial[mask][k - 1], partial[mask | (1 << (k - 1))][k - 1]);
                else {
                    partial[mask][k] = partial[mask][k - 1];
                    if (partial[mask ^ (1 << (k - 1))][k - 1] != INT_MAX)
                        partial[mask][k] = min(partial[mask][k], partial[mask ^ (1 << (k - 1))][k - 1] + 1);
                }
            }
        }
        for (int mask = 0; mask < (1 << n); mask++)
            dp[t][mask] = partial[mask][n] + (partial[mask][n] == INT_MAX ? 0 : cnt(mask | block[j]));
    }
    cout << *min_element(dp[m & 1], dp[m & 1] + (1 << n));


    return 0;
}

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