# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
850238 | Tai_xiu | Selotejp (COCI20_selotejp) | C++14 | 1026 ms | 11504 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[1003][11];
vector<int>lt[1003],lt1[1003];
int dp[1003][1<<10],gt[1024][1024],val[1024];
void init()
{
for (int i=0;i<(1<<m);i++){
int tam=i;
int cnt=0;
if (tam&1)
cnt++;
for (int j=1;j<m;j++){
if (((i>>j)&1) && (((i>>(j-1))&1)==0))
cnt++;
}
val[i]=cnt;
}
for (int i=0;i<(1<<m);i++){
for (int j=0;j<(1<<m);j++){
int tam=j,cnt=0;
for (int k=0;k<m;k++){
if (((i>>k)&1)==0 && ((j>>k)&1)==1){
cnt++;
tam^=(1<<k);
}
}
gt[i][j]=val[tam]+cnt;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
init();
for (int i=0;i<=n;i++){
for (int j=0;j<(1<<m);j++)
dp[i][j]=1e9;
}
for (int i=1;i<=n;i++){
for (int j=0;j<m;j++)
cin>>a[i][j];
}
for (int i=0;i<m;i++)
a[n+1][i]='.';
for( int i=1;i<=n;i++){
for (int j=0;j<(1<<m);j++){
bool kt=true;
for (int k=0;k<m;k++){
if ((( j>>k)&1)==1 && a[i][k]=='.' )
{
kt=false;
break;
}
if ((((j>>k)&1)==0) && a[i+1][k]=='.' && a[i][k]=='#'){
kt=false;
break;
}
}
if (kt){
lt[i].push_back(j);
int tam=j;
for (int k=0;k<m;k++){
if (((j>>k)&1)==0 && a[i][k]=='.')
tam|=(1<<k);
}
lt1[i].push_back(tam);
}
}
}
/*
for (int i=1;i<=n;i++){
for (int j:lt[i])
cout<<j<<" ";
cout<<endl;
}
10 11 14 15
10 11 14 15
2 3 6 7 10 11 14 15
for (int i=2;i<=n;i++){
for (int mask:lt[i]){
for (int premask:)
}
}
cout<<dp[n][(1<<m)-1];*/
/*
for (int i=1;i<=n;i++){
for (int mask:lt[i]){
int tam=mask;
for (int j=0;j<m;j++){
if (((mask>>j)&1)==0 && a[i][j]=='.')
tam|=(1<<j);
}
lt1[i].push_back(tam);
}
}*/
/*
for (int i=1;i<=n;i++){
for (int j:lt1[i])
cout<<j<<" ";
cout<<endl;
}*/
for (int i=0;i<lt[1].size();i++){
dp[1][lt1[1][i]]=val[lt[1][i]];
}
for (int i=2;i<=n;i++){
for (int mask=0;mask<lt[i].size();mask++){
for (int premask=0;premask<lt[i-1].size();premask++){
dp[i][lt1[i][mask]]=min(dp[i][lt1[i][mask]],dp[i-1][lt1[i-1][premask]]+gt[lt1[i-1][premask]][lt[i][mask]]);
}
}
}
cout<<dp[n][(1<<m)-1];
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |