Submission #1154486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154486		simuyu	Selotejp (COCI20_selotejp)	C++20	0 / 110	0 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define INF 1000000009

int n, m;
bool grid[1005][15];
int max_bm;
ll dp[1005][15][37];

/*
// outputs lowest possible cost
ll dp(int i, int j, int bm) { // i and j are current position, bm is a bitmask representing direction of tape in the latest one of each of the 10 columns
    // in the bitmask, let 1 be vertical and 0 be horizontal direction, for each bit.

    // i and j are 1-indexed, and so is grid and memo.

    // base case:
    if (i==0) return 0; // at row 0, there's nothing to put (as it's fake), so 0 actions are needed.

    // check memo
    if (memo[i][j][bm] != -1) return memo[i][j][bm];

    // transition:


}
*/


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

    //
    cin >> n >> m;
    char c;
    // index 0s of grid are to be ignored - outer border kind of thing
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            cin >> c;
            grid[i][j] = (c=='#');
        }
    }
    // initialize border of grid
    for (int i=0; i<=n+1; i++) {
        grid[i][0] = false;
    }
    for (int i=0; i<=n+1; i++) {
        grid[i][m+1] = false;
    }
    for (int j=0; j<=m+1; j++) {
        grid[0][j] = false;
    }
    for (int j=0; j<=m+1; j++) {
        grid[n+1][j] = false;
    }

    // run DP
    max_bm = 1<<m;


    // initialize dp table
    for (int i=0; i<=n+1; i++) {
        for (int j=0; j<=m+1; j++) {
            for (int bm=0; bm<=max_bm; bm++) {
                dp[i][j][bm] = INF;
            }
        }
    }


    // initialize first row
    for (int j=0; j<=m+1; j++) {
        dp[0][j][0] = 0; // as it costs nothing
        // the rest are all INF as it's impossible for them to be activated
    }


    // define 1 to be vertical, 0 to be horizontal, and if it's not taped then just put 0 for convenience
    int can_be_vertical = 0; // a bitmask for which ones are taped

    ll best;

    // transition
    for (int i=1; i<=n; i++) {
        // update can_be_vertical
        if (grid[i][1] != grid[i-1][1]) can_be_vertical ^= (1);

        // j=1 case

        // try all the possible newbms
        for (int newbm=can_be_vertical; newbm!=0; newbm = (newbm-1)&can_be_vertical) {
            // now all the possible newbm values are a possible new bm - except 0 is not here
            if (!grid[i][1]) {
                best = min(dp[i-1][m][newbm], dp[i-1][m][newbm^1]);

            } else if (newbm & (1)) { // if newbm is vertical at this pos
                // either follow a case where the one above is vertical, with no cost
                best = dp[i-1][m][newbm];
                // or the one above is horizontal, with +1 cost
                best = min(best, dp[i-1][m][newbm ^ (1)] + 1 );

            } else { // newbm is horizontal at this pos
                // since it's at the start, as long as grid is true, it's adding by one
                best = min(dp[i-1][m][newbm], dp[i-1][m][newbm^(1)]) + (int)(grid[i][1]);
            }
            dp[i][1][newbm] = best;
        }
        // newbm = 0 also should be considered - newbm is horizontal at this pos
        dp[i][1][0] = min(dp[i-1][m][0], dp[i-1][m][0^1]) + (int)(grid[i][1]);

        // everything else is just -1, as initialized, and indeed, it's impossible.

        // now, for j!=1
        for (int j=2; j<=m; j++) {
            if (grid[i][j] != grid[i-1][j]) can_be_vertical ^= (1<<(j-1));

            //cout << "I " << i << ", J " << j << "; CAN_BE_VERTICAL=" << can_be_vertical << endl;

            for (int newbm=can_be_vertical; newbm!=0; newbm = (newbm-1)&can_be_vertical) {
                // now all the possible newbm values are a possible new bm - except 0 is not here
                // if current one doesn't exist, just take min of the two possible ones above
                if (!grid[i][j]) {
                    best = min(dp[i][j-1][newbm], dp[i][j-1][newbm^(1<<(j-1))]);

                } else if (newbm & (1<<(j-1))) { // new bitmask is vertical here
                    // either join together with previous vertical one at no cost
                    best = dp[i][j-1][newbm];
                    // or previous is horizontal, +1 cost
                    best = min(best, dp[i][j-1][newbm^(1<<(j-1))]+1);
                } else {
                    // new bitmask is horizontal here
                    // if the one on the left is vertical, +1 cost.
                    if ( (newbm & (1<<(j-2))) || (!grid[i][j-1]) ) { // the one on the left is vertical, OR the one on left doesn't exist
                        // then we can't try joining with it. +1 cost.
                        best = min( dp[i][j-1][newbm] , dp[i][j-1][newbm|(1<<(j-1))] ) + 1; // above can be horizontal or vertical
                    } else { // the one on the left is either no tape or horizontal
                        // if it exists - it's horizontal
                        // the one on the left exists - we join with it horizontally at 0 cost
                        best = min( dp[i][j-1][newbm] , dp[i][j-1][newbm^(1<<(j-1))] ); // above can be horizontal or vertical

                    }
                }

                dp[i][j][newbm] = best;
                //cout << newbm << "->" << best << ' ';
            }
            // or newbm = 0 - joined horizontally, top can be either
            dp[i][j][0] = min(dp[i][j-1][0], dp[i][j-1][1<<(j-1)]) + (int)(grid[i][j] &&(!grid[i][j-1]));
            //cout << 0 << "->" << dp[i][j][0] << endl;
        }

    }

    // debug: display the dp table with newbm=0
    /*cout << "DEBUG: DP TABLE: " << endl;
    for (int i=0; i<=n+1; i++) {
        for (int j=0; j<=m+1; j++) {
            cout << dp[i][j][2] << ' ';
        }
        cout << endl;
    }
    cout << endl;*/


    ll res=LLONG_MAX;
    for (int bm=0; bm<max_bm; bm++) { // get best possible value by trying each bm
        res = min(res, dp[n][m][bm]);
    }

    cout << res << endl;


    return 0;
}

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