Submission #931533

#	Time	Username	Problem	Language	Result	Execution time	Memory
931533		Whisper	Selotejp (COCI20_selotejp)	C++17	110 / 110	18 ms	1624 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define pii pair<int , int>
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 1e3 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int nCol, nRow;
char a[MAX][MAX];
void Whisper(){
    cin >> nRow >> nCol;
    REP(i, nRow) REP(j, nCol) cin >> a[i][j];

    vector<int> F(MASK(nCol)), G(MASK(nCol), INF);
    G[0] = 0;
    REP(i, nRow) REP(j, nCol){
        for (int msk = 0; msk < MASK(nCol); ++msk){
            if (a[i][j] == '.'){
                if (BIT(msk, j)) F[msk] = INF;
                else F[msk] = min(G[msk], G[msk ^ MASK(j)]);
            }
            else{
                if (BIT(msk, j)){
                    F[msk] = min(G[msk], G[msk ^ MASK(j)] + 1);
                }
                else{
                    F[msk] = min(G[msk], G[msk ^ MASK(j)]);
                    if (j == 0 || a[i][j - 1] == '.' || BIT(msk, j - 1)) F[msk]++;
                }
            }
        }
        swap(F, G);
    }
    int ans = INF;
    for (int msk = 0; msk < MASK(nCol); ++msk){
        minimize(ans, G[msk]);
    }
    cout << ans;
    /*
        using dp[i][j][msk] as the minimum that the state i and j is the current row and column
        and the mask that represents what happened on the last m square, the current square, squares
        that are in the current row and on the left side, and square is in the previous row that are
        on the right side of the current square

        bit 0 mean that the row j is covered by a horizontal piece of tape
        bit 1 mean that the row j is covered by a vertical piece of tape

        1. a[i][j] = '.'
            dp[i][j][msk] = min(dp[i][j - 1][msk], dp[i][j - 1][msk ^ MASK(j) + 1]
        2. a[i][j] != '.'
            if (the j - th bit is 1)
                dp[i][j][msk] = min(dp[i][j - 1][msk]) // the previous square has the same state with current
                dp[i][j][msk] = min(dp[i][j - 1][msk ^ MASK(j)] + 1) // (the previous square is covered by a horizontal piece of tape
                so we make a new vertical piece of tap -> + 1)
            if (the j - th bit is 0)
                dp[i][j][msk] = min(dp[i][j][msk, dp[i][j][msk ^ MASK(j)] (update for new state)
                if (i == 0 || s[i][j - 1] == '.' || BIT(msk, j - 1)) dp[i][j][msk]++ (make a new horizontal piece of tape)
        3. we can also optimize the memory by using two array F and G
        F(msk) : the minimum tape we need to cover all the close till i row and j column
        G(msk) : the minimum tape we need to cover all the colose till i row and j - 1 column
    */
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

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