Submission #1097888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097888		0pt1mus23	Selotejp (COCI20_selotejp)	C++14	110 / 110	18 ms	604 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ins insert      
#define pb push_back

#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
#define _ << " " <<
mt19937 rng(time(0));

const int mod = 998244353,
        sze = 1e3 +23,
        inf = 1e9,    
        L = 10;
void _0x0(){
    int n,m;
    cin>>n>>m;
    vector<int> last(1<<m,inf),curr(1<<m,0);
    last[0]=0;
    vector<char> arr[n];
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(auto v:s){
            arr[i].pb(v);
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int mask=0;mask<(1<<m);mask++){

                if(mask & (1<<j)){
                    if(arr[i][j]=='.'){
                        curr[mask]=inf;
                    }
                    else{
                        curr[mask]=min(last[mask], last[mask ^ (1<<j)] +1);
                    }
                }
                else{
                    curr[mask]=min(last[mask], last[mask ^ (1<<j)]);
                    if(arr[i][j]=='#' && (j ==0 || ( arr[i][j-1]=='.' || (mask & (1<<(j-1)))) ) ){
                        curr[mask]++;
                    }
                }
            }
            last=curr;
        }
    }

    putr(*min_element( all(last) ));

}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1;
    // cin>>tt;
    while(tt--){
        _0x0();
    }
 
    return 0;
}

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