Submission #684828

#	Time	Username	Problem	Language	Result	Execution time	Memory
684828		vjudge1	Selotejp (COCI20_selotejp)	C++17	110 / 110	58 ms	44884 KiB

Main

#include<bits/stdc++.h>
#define INF 1e9+7
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pipii pair<int,pii>
#define plpll pair<ll,pll>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ins insert
#define ln '\n'
#define all(v) v.begin(),v.end()
using namespace std;

void solve(){
   int n,m;
   cin>>n>>m;
   vector<string>inp(n);
   for(string &to:inp){
     cin>>to;
   }
   vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(m+1,vector<int>(1<<m,INF)));
   for(int p=0;p<(1<<m);p++){
       dp[0][0][p]=0;
   }
   for(int i=0;i<n;i++){
       for(int j=0;j<m;j++){
           for(int p=0;p<(1<<m);p++){
               if(inp[i][j]=='.'){
                    dp[i][j+1][p]=min(dp[i][j+1][p],dp[i][j][p]);
                    dp[i][j+1][p^(1<<j)]=min(dp[i][j+1][p^(1<<j)],dp[i][j][p]);
               }
               else{
                    int q=p|(1<<j);
                    if(j&&inp[i][j-1]=='#'&&p&(1<<(j-1))){
                        dp[i][j+1][q]=min(dp[i][j+1][q],dp[i][j][p]);
                    }
                    else{
                        dp[i][j+1][q]=min(dp[i][j+1][q],dp[i][j][p]+1);
                    }
                    q^=(1<<j);
                    if(i&&inp[i-1][j]=='#'&&!(p&(1<<j))){
                        dp[i][j+1][q]=min(dp[i][j+1][q],dp[i][j][p]);
                    }
                    else{
                        dp[i][j+1][q]=min(dp[i][j+1][q],dp[i][j][p]+1);
                    }
               }
           }
       }
       for(int p=0;p<(1<<m);p++){
           dp[i+1][0][p]=dp[i][m][p];
       }
   }
   int res=INF;
   for(int p=0;p<(1<<m);p++){
       res=min(res,dp[n][0][p]);
   }
   cout<<res<<ln;
}

int main ()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   solve();
}
/*
10 10
0 1 10 100
1 1 5 3
1 7 9 8
0 1 10 9
2 1 2 3
2 9 4
0 1 10 100
1 1 10 2
0 1 10 1000
2 1 5 2
0 1 6
1
0
ll
10
1 2
2 4
4 8
4 9
2 5
1 3
3 6
6 10
3 7
*/

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