Submission #691963

#	Time	Username	Problem	Language	Result	Execution time	Memory
691963		Neos	Selotejp (COCI20_selotejp)	C++14	110 / 110	45 ms	40796 KiB

Main

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

#define fi first
#define se second
#define sz(x) (int)x.size()
#define M(x) (1ll << (x))
#define getBit(x, i) ((x) >> (i) & 1)
#define rep(i, b, e) for (ll i = (b); i <= (e); i++)
#define rrep(i, b, e) for (ll i = (b); i >= (e); i--)

typedef long long ll;
typedef pair<ll, ll> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 1e3 + 7, M = 10;
int n, m, a[N][M + 2], f[N][M][1 << M];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    rep(i, 1, n) {
        rep(j, 0, m - 1) {
            char c; cin >> c;
            if (c == '#') a[i][j] = 1;
        }
    }

    memset(f, 0x3f, sizeof f);
    int ans = 2e9;
    rep(j, 0, (1 << m) - 1) f[0][m - 1][j] = 0;
    rep(i, 1, n) rep(j, 0, m - 1) rep(k, 0, (1 << m) - 1) {
        if (a[i][j]) {
            // verticle
            if (getBit(k, j)) {
                if (j == 0) {
                    minimize(f[i][j][k], f[i - 1][m - 1][k ^ M(j)] + 1);
                    if (a[i - 1][j]) minimize(f[i][j][k], f[i - 1][m - 1][k]);
                }
                else {
                    minimize(f[i][j][k], f[i][j - 1][k ^ M(j)] + 1);
                    if (a[i - 1][j]) minimize(f[i][j][k], f[i][j - 1][k]);
                }
            } else { // horizontal
                if (j == 0) {
                    f[i][j][k] = min(f[i - 1][m - 1][k ^ M(j)], f[i - 1][m - 1][k]) + 1;
                }
                else {
                    if (!a[i][j - 1] || getBit(k, j - 1)) {
                        f[i][j][k] = min(f[i][j - 1][k], f[i][j - 1][k ^ M(j)]) + 1;
                    }
                    if (a[i][j - 1] && !getBit(k, j - 1))
                        f[i][j][k] = min(f[i][j - 1][k ^ M(j)], f[i][j - 1][k]);
                }
            }
        }
        else {
            if (j == 0) f[i][j][k] = min(f[i - 1][m - 1][k], f[i - 1][m - 1][k ^ M(j)]);
            else f[i][j][k] = min(f[i][j - 1][k], f[i][j - 1][k ^ M(j)]);
        }
        if (i == n && j == m - 1) minimize(ans, f[i][j][k]);
    }
    cout << ans;
}

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