제출 #1197290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197290		_callmelucian	Selotejp (COCI20_selotejp)	C++17	110 / 110	31 ms	584 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 dp[2][1 << 11][11];
char ch[1010][11];

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

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

    /// read input
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> ch[i][j];
        ch[i][0] = ch[i][m + 1] = '.';
    }
    for (int j = 0; j <= m + 1; j++) ch[n + 1][j] = '.';

    /// base cases
    for (int mask = 1; mask < (1 << m); mask++)
        dp[0][mask << 1][m] = INT_MAX;

    /// broken profile DP
    for (int i = 1; i <= n + 1; i++) {
        int t = i & 1;

        // refill state
        for (int msk = 0; msk < (1 << m); msk++)
            fill(dp[t][msk << 1], dp[t][msk << 1] + m + 1, INT_MAX);

        // compute first state
        for (int msk = 0; msk < (1 << m); msk++)
            dp[t][msk << 1][0] = dp[t ^ 1][msk << 1][m];

        // compute other state
        for (int j = 1; j <= m; j++) {
            for (int msk = 0; msk < (1 << m); msk++) {
                int mask = msk << 1;
                if (getCur(mask, j) && ch[i][j] == '.') continue;
                if (getCur(mask, j)) // column j covered
                    dp[t][mask][j] = min(dp[t][mask][j - 1], dp[t][mask ^ (1 << j)][j - 1]);
                else {
                    char pre = (getCur(mask, j - 1) ? '.' : ch[i][j - 1]);
                    int cost = (ch[i][j] == '#' && pre == '.');
                    if (dp[t][mask][j - 1] != INT_MAX)
                        dp[t][mask][j] = min(dp[t][mask][j], dp[t][mask][j - 1] + cost);
                    if (dp[t][mask ^ (1 << j)][j - 1] != INT_MAX)
                        dp[t][mask][j] = min(dp[t][mask][j], dp[t][mask ^ (1 << j)][j - 1] + cost + 1);
                }
            }
        }

//        cout << "table " << i << ":\n";
//        for (int j = 0; j <= m; j++) {
//            for (int mask = 0; mask < (1 << m); mask++) cout << dp[t][mask << 1][j] << " ";
//            cout << "\n";
//        }
    }
    cout << dp[(n + 1) & 1][0][m];

    return 0;
}

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