제출 #1247943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247943		dfhdfhdsf	Selotejp (COCI20_selotejp)	C++20	70 / 110	1096 ms	460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
static const int INF = 1e9;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> row_mask(n);
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        int mask = 0;
        for(int j = 0; j < m; j++){
            if (s[j] == '#')
                mask |= (1 << j);
        }
        row_mask[i] = mask;
    }

    // Precompute popcount for masks up to 2^m
    int M = 1 << m;
    vector<int> popc(M);
    for(int mask = 1; mask < M; mask++){
        popc[mask] = popc[mask >> 1] + (mask & 1);
    }

    // Precompute horizontal segments for every possible H mask (length m)
    // segs[H] = số chuỗi con liên tiếp trong H
    vector<int> segs(M, 0);
    for(int mask = 0; mask < M; mask++){
        int cnt = 0;
        for(int j = 0; j < m; j++){
            if ((mask & (1 << j)) && (j == 0 || !(mask & (1 << (j-1)))))
                cnt++;
        }
        segs[mask] = cnt;
    }

    // DP arrays
    vector<int> dp(M, INF), newdp(M, INF);
    // ban đầu, trước hàng 0 ta chưa mở dọc ở đâu, chi phí = 0
    dp[0] = 0;

    // chuyển DP qua từng hàng
    for(int i = 0; i < n; i++){
        int R = row_mask[i];
        // reset newdp
        fill(newdp.begin(), newdp.end(), INF);

        // với mỗi cấu hình mở dọc prev_mask
        for(int prev_mask = 0; prev_mask < M; prev_mask++){
            if (dp[prev_mask] == INF) continue;
            // chỉ xét next_mask là conmask của R
            // enumerate submasks of R:
            //   for(int next_mask = R; ; next_mask = (next_mask-1) & R) { ... if(next_mask==0) break; }
            // trong đó có cả next_mask=0, cho nên ta dùng do-while
            int next_mask = R;
            do {
                // chi phí khởi các băng dọc mới:
                //   mỗi bit 1 ở next_mask mà prev_mask có 0 ⇒ +1
                int start_new = popc[next_mask & ~prev_mask];
                // chi phí ngang:
                int H = R ^ next_mask;
                int cost_h = segs[H];
                int cost = dp[prev_mask] + start_new + cost_h;
                // cập nhật
                if (cost < newdp[next_mask])
                    newdp[next_mask] = cost;

                if (next_mask == 0) break;
                next_mask = (next_mask - 1) & R;
            } while(true);
        }

        // chuyển sang hàng tiếp
        dp.swap(newdp);
    }

    // đáp án: min dp[mask] ở hàng cuối (không tính thêm gì khi đóng dọc)
    int ans = *min_element(dp.begin(), dp.end());
    cout << ans << "\n";
    return 0;
}

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