Submission #1223318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223318		overwatch9	Selotejp (COCI20_selotejp)	C++20	110 / 110	192 ms	156640 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1001;
const int maxm = 11;
int dp[maxn][maxm][(1 << maxm)][2];
bool ready[maxn][maxm][(1 << maxm)][2];
vector <string> grid;
int n, m;
// dp[i][j][mask][is the last square covered by a piece of horizontal tape or not]
// in mask: 1 is if the square is covered by vertical tape
// in mask: 0 is if the square is not covered by vertical tape
int solve(int i, int j, int mask, bool horizontal) {
    if (i >= n)
        return 0;
    if (ready[i][j][mask][horizontal])
        return dp[i][j][mask][horizontal];
    int ans = 1e9;
    if (grid[i][j] == '#') { // closed window
        int mask2 = mask;
        if (horizontal) {
            // continue the horizontal tape
            mask2 = (mask2 << 1);
            mask2 &= ((1 << m) - 1);
            if (j+1 < m)
                ans = min(ans, solve(i, j+1, mask2, true));
            else
                ans = min(ans, solve(i+1, 0, mask2, false));
        }
        // see if the vertical piece can be continued
        mask2 = mask;
        mask2 = (mask2 << 1);
        if (mask2 & (1 << m)) {
            mask2 &= ((1 << m) - 1);
            mask2++;
            if (j+1 < m)
                ans = min(ans, solve(i, j+1, mask2, false));
            else
                ans = min(ans, solve(i+1, 0, mask2, false));
        }
        // start a vertical piece
        mask2 = mask;
        mask2 = (mask2 << 1);
        mask2 &= ((1 << m) - 1);
        mask2++;
        if (j+1 < m)
            ans = min(ans, solve(i, j+1, mask2, false) + 1);
        else
            ans = min(ans, solve(i+1, 0, mask2, false) + 1);

        // start a horizontal piece
        mask2 = mask;
        mask2 = (mask2 << 1);
        mask2 &= ((1 << m) - 1);
        if (j+1 < m)
            ans = min(ans, solve(i, j+1, mask2, true) + 1);
        else
            ans = min(ans, solve(i+1, 0, mask2, false) + 1);

    } else { // open window
        int mask2 = mask;
        mask2 = (mask2 << 1);
        mask2 &= ((1 << m) - 1);
        if (j+1 < m)
            ans = min(ans, solve(i, j+1, mask2, false));
        else
            ans = min(ans, solve(i+1, 0, mask2, false));
    }
    dp[i][j][mask][horizontal] = ans;
    ready[i][j][mask][horizontal] = true;
    return ans;
}
int main() {
    cin >> n >> m;
    grid.resize(n+1);
    for (int i = 0; i < n; i++)
        cin >> grid[i];
    cout << solve(0, 0, 0, 0) << '\n';
}

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