Submission #377415

#	Time	Username	Problem	Language	Result	Execution time	Memory
377415		VEGAnn	Selotejp (COCI20_selotejp)	C++14	110 / 110	369 ms	4460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int oo = 2e9;
const int N = 1010;
const int M = 10;
const int PW = 10;
const int HPW = 233;
const int md = int(1e9) + 7;
int f[N][(1 << M)], n, m;
string s;

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i <= n; i++)
    for (int j = 0; j < (1 << m); j++)
        f[i][j] = oo;

    f[0][0] = 0;

    for (int i = 1; i <= n; i++){
        cin >> s;

        int cur = 0;

        for (int j = 0; j < m; j++)
            if (s[j] == '#')
                cur += (1 << j);

        for (int old = 0; old < (1 << m); old++)
        for (int msk = old; ; msk = ((msk - 1) & old)){
            f[i - 1][msk] = min(f[i - 1][msk], f[i - 1][old]);

            if (msk == 0) break;
        }

        for (int nw = 0; nw < (1 << m); nw++){
            bool ok = 1;

            for (int j = 0; j < m; j++)
                if (s[j] == '.' && (nw & (1 << j))){
                    ok = 0;
                    break;
                }

            if (!ok) continue;

            int base = 0;

            for (int j = 0; j < m; j++)
                if (nw & (1 << j))
                    base++;
                else {
                    if (cur & (1 << j)){
                        if (!(j > 0 && (cur & (1 << (j - 1))) && (!(nw & (1 << (j - 1))))))
                            base++;
                    }
                }

            for (int pre = nw; ; pre = ((pre - 1) & nw)){
                int nf = f[i - 1][pre];

                if (nf == oo) {
                    if (pre == 0)
                        break;

                    continue;
                }

                nf += base - __builtin_popcount(pre & nw);

                f[i][nw] = min(f[i][nw], nf);

                if (pre == 0) break;
            }
        }
    }

    int ans = oo;

    for (int msk = 0; msk < (1 << m); msk++)
        ans = min(ans, f[n][msk]);

    cout << ans;

    return 0;
}

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