제출 #1247939

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

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;

#pragma GCC optimize("Ofast,unroll-loops")

int n, m, maxMask;
vector<string> a;
int dp_prev[1<<10], dp_cur[1<<10];
vector<int> submasks[1<<10];
int hcost[1<<10];

inline int popc(int x) { return __builtin_popcount(x); }

int run(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    a.resize(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    maxMask = (1<<m) - 1;

    // Tiền xử lý tất cả submasks
    for(int mask = 0; mask <= maxMask; mask++){
        submasks[mask].clear();
        int s = mask;
        do {
            submasks[mask].push_back(s);
            if(s == 0) break;
            s = (s-1) & mask;
        } while(true);
    }

    // Khởi dp_prev
    for(int mask = 0; mask <= maxMask; mask++) dp_prev[mask] = INF;
    dp_prev[0] = 0;

    // DP theo hàng
    for(int row = 0; row < n; row++){
        // tính row_mask
        int row_mask = 0;
        for(int j = 0; j < m; j++){
            if(a[row][j] == '#') row_mask |= (1<<j);
        }

        // tính hcost[u] cho u từ 0..maxMask
        // hcost[u] = số đoạn ngang khi đã che các cột thuộc u, cần che những bit của row_mask & ~u
        for(int u = 0; u <= maxMask; u++){
            int seg = 0;
            bool in_seg = false;
            int need_mask = row_mask & ~u;
            for(int j = 0; j < m; j++){
                if(need_mask & (1<<j)){
                    if(!in_seg){
                        seg++;
                        in_seg = true;
                    }
                } else {
                    in_seg = false;
                }
            }
            hcost[u] = seg;
        }

        // reset dp_cur
        for(int mask = 0; mask <= maxMask; mask++){
            dp_cur[mask] = INF;
        }

        // chuyển dp
        for(int mask_in = 0; mask_in <= maxMask; mask_in++){
            int base = dp_prev[mask_in];
            if(base >= INF) continue;
            // mask_in phải là con mask của row_mask (không kéo xuống ở ô '.')
            if(mask_in & ~row_mask) continue;

            // cho mọi mask_out con của row_mask
            // submasks[row_mask] đã tiền tính
            for(int mask_out : submasks[row_mask]){
                // tính cost
                // mới dán dọc: bits in mask_out but not in mask_in
                int vert_new = popc(mask_out & ~mask_in);
                // union để lấy hcost
                int u = mask_in | mask_out;
                int cost = base + vert_new + hcost[u];

                // cập nhật
                if(cost < dp_cur[mask_out]){
                    dp_cur[mask_out] = cost;
                }
            }
        }

        // chuyển đổi
        memcpy(dp_prev, dp_cur, sizeof dp_cur);
    }

    // kết quả
    int ans = INF;
    for(int mask = 0; mask <= maxMask; mask++){
        ans = min(ans, dp_prev[mask]);
    }
    cout << ans << "\n";

    return 0;
}

int main(){
    return run();
}

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