제출 #1247935

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

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define ALL(x) (x).begin(), (x).end()
#define isz(x) (int)(x).size()
const int INF = 1000000000;

int n, m;
vector<string> a;
int maxMask;

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

void solve(){
    cin >> n >> m;
    a.resize(n);
    FOR(i,0,n-1){
        cin >> a[i];
    }
    maxMask = (1<<m) - 1;
    // dp_prev[mask] = tối thiểu số mảnh băng để xử lý đến hàng trước,
    // với các đoạn dọc "đang mở" là mask
    vector<int> dp_prev(1<<m, INF), dp_cur(1<<m, INF);
    vector<int> prev_masks;
    dp_prev[0] = 0;
    prev_masks.push_back(0);
    
    FOR(row,0,n-1){
        int row_mask = 0;
        FOR(j,0,m-1){
            if (a[row][j] == '#') row_mask |= (1<<j);
        }
        // reset dp_cur
        fill(ALL(dp_cur), INF);
        vector<int> cur_masks;
        
        // enumerate tất cả submask của row_mask làm mask_out
        for(int mask_out = row_mask; ; mask_out = (mask_out-1) & row_mask){
            // với mỗi mask_in khả dĩ từ prev_masks
            for(int mask_in : prev_masks){
                // nếu mask_in có bit ở vị trí '.' thì bỏ
                if (mask_in & ~row_mask) continue;
                int base = dp_prev[mask_in];
                // khởi động cost = dp_prev
                int cost = base;
                
                // 1) mảnh băng dọc mới: những bit 1 ở mask_out nhưng 0 ở mask_in
                int new_vert = popc(mask_out & ~mask_in);
                cost += new_vert;
                
                // 2) mảnh băng ngang: đếm số đoạn liên tiếp ở hàng này
                //    tại các vị trí # mà không có băng dọc (cả từ trên và từ dưới)
                int segs = 0;
                bool in_seg = false;
                FOR(j,0,m-1){
                    bool need = ( (row_mask>>j)&1 )   // đây là ô #
                                && !( ((mask_in|mask_out)>>j)&1 );
                    if (need){
                        if (!in_seg){
                            segs++;
                            in_seg = true;
                        }
                    } else {
                        in_seg = false;
                    }
                }
                cost += segs;
                
                // cập nhật
                if (cost < dp_cur[mask_out]){
                    dp_cur[mask_out] = cost;
                }
            }
            if (mask_out == 0) break;
        }
        
        // thu lại các mask có dp_cur < INF
        cur_masks.clear();
        FOR(mask,0,maxMask){
            if (dp_cur[mask] < INF){
                cur_masks.push_back(mask);
            }
        }
        // chuyển sang bước kế
        dp_prev.swap(dp_cur);
        prev_masks.swap(cur_masks);
    }
    
    // kết quả = min dp_prev[mask] với mọi mask
    int ans = INF;
    for(int mask : prev_masks){
        ans = min(ans, dp_prev[mask]);
    }
    cout << ans << "\n";
}

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

    solve();
    return 0;
}

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