Submission #465531

#	Time	Username	Problem	Language	Result	Execution time	Memory
465531		TheScrasse	Selotejp (COCI20_selotejp)	C++17	110 / 110	375 ms	8420 KiB

Main

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

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 1010
#define maxm 11
#define maxb 1034

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll mk0, mk1, mk2, mka, dp[maxn][maxb], x;
char mt[maxn][maxm];

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

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> n >> m;
    for (i = 1; i <= n; i++) {
        for (j = 0; j <= m - 1; j++) {
            cin >> mt[i][j];
        }
    }

    for (i = 0; i <= n; i++) {
        for (mk1 = 0; mk1 < (1 << m); mk1++) {
            dp[i][mk1] = INF;
        }
    }
    dp[0][0] = 0;

    for (i = 1; i <= n; i++) {
        mk0 = 0;
        for (j = 0; j <= m - 1; j++) {
            if (mt[i][j] == '#') mk0 += (1 << j);
        }

        for (mk1 = mk0;; mk1 = (mk1 - 1) & mk0) {
            mka = (mk0 & (~mk1)); k = 0;
            for (j = 0; j <= m - 1; j++) {
                if (((mka >> j) & 1) == 0) continue;
                if (j == 0 || ((mka >> (j - 1)) & 1) == 0) k++;
            }

            for (mk2 = mk1;; mk2 = (mk2 - 1) & mk1) {
                x = __builtin_popcountll(mk1) - __builtin_popcountll(mk1 & mk2);
                x += dp[i - 1][mk2];
                dp[i][mk1] = min(dp[i][mk1], k + x);
                if (mk2 == 0) break;
            }
            if (mk1 == 0) break;
        }

        for (mk1 = mk0;; mk1 = (mk1 - 1) & mk0) {
            for (mk2 = mk1;; mk2 = (mk2 - 1) & mk1) {
                dp[i][mk2] = min(dp[i][mk2], dp[i][mk1]);
                if (mk2 == 0) break;
            }
            if (mk1 == 0) break;
        }
    }

    /* for (i = 0; i <= n; i++) {
        for (mk1 = 0; mk1 < (1 << m); mk1++) {
            cout << dp[i][mk1] << ' ';
        }
        cout << nl;
    } */

    cout << dp[n][0] << nl;

    return 0;
}

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