Submission #1093253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093253		anhthi	Selotejp (COCI20_selotejp)	C++14	70 / 110	1049 ms	4696 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define clz __builtin_clzll
#define ctz __builtin_ctzll
#define popcount __builtin_popcount
#define lg(x) (63 - clz(x))
 
template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        return false;
    }
template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        return false;
    }
template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a)); a.resize(unique(all(a)) - a.begin());
    }
 
const ll oo = (ll) 1e17;
const int inf = (int) 1e9, mod = (int) 1e9 + 7;
 
const int mxn = (int) 1e3 + 5, mxm = (int) 10;
int n, m;
int a[mxn][mxm];
 
int subMask[mxn];
int f[mxn][MASK(mxm)];
 
int stack_mask[MASK(mxm)];
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    for (int j = 0; j < m; ++j) {
        char c; cin >> c;
        a[i][j] = (c == '#');
        subMask[i] += a[i][j] * MASK(j);
    }
 
    for (int mask = 0; mask < MASK(m); ++mask) {
        bool ok = false;
        for (int i = 0; i < m; ++i) {
            if (BIT(mask, i)) ok = true;
            else {
                if (ok) stack_mask[mask]++;
                ok = false;
            }
        }
        if (ok) stack_mask[mask]++;
    }
 
    memset(f, 0x3f, sizeof f);
 
    f[0][0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < MASK(m); ++mask) if (f[i][mask] < inf) {
            int rev = ~mask & (MASK(m) - 1) & subMask[i+1];
            for (int sub = rev; ; sub = (sub - 1) & rev) {
                int cur = mask & subMask[i+1];
                for (int sub_mask = cur; ; sub_mask = (sub_mask - 1) & cur) {
                    minimize(f[i+1][sub | sub_mask], f[i][mask] + popcount(sub));
                    if (sub_mask == 0) break;
                }
                if (sub == 0) break;
            }
        }
        for (int mask = 0; mask < MASK(m); ++mask) {
            int rev = ~mask & (MASK(m) - 1);
            rev &= subMask[i+1];
            f[i+1][mask] += stack_mask[rev];
        }
    }
 
    int ans = inf;
    for (int mask = 0; mask < MASK(m); ++mask)
        minimize(ans, f[n][mask]);
 
    cout << ans << '\n';
 
    return 0;
}

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