Submission #883944

#	Time	Username	Problem	Language	Result	Execution time	Memory
883944		HossamHero7	Selotejp (COCI20_selotejp)	C++14	110 / 110	243 ms	41976 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int dp[1005][10][(1<<10)];
int n,m;
vector<string> v;
int off(int mask,int l,int r){
    int x = (1<<(r - l + 1)) - 1;
    x <<= l;
    return mask&(~x);
}
int solve(int i,int j,int mask){
    if(i == n) return 0;
    int &ret = dp[i][j][mask];
    if(~ret) return ret;
    if(j == m) return ret = solve(i+1,0,mask);
    ret = 1e9;
    if(v[i][j] == '#') ret = min(ret , solve(i,j+1,mask|(1<<j)) + (1-(mask>>j)&1));
    else ret = min(ret , solve(i,j+1,off(mask,j,j)));
    for(int k=j;k<m;k++){
        if(v[i][k] == '.') break;
        if(k+2 == m+1) ret = min(ret , solve(i+1,0,off(mask,j,m-1)) + 1);
        else if(k + 2 == m) ret = min(ret , solve(i+1,0,off(mask,j,m-1)|((1<<m-1))*(v[i][m-1]=='#')) + ((1-((mask>>k+1)&1))&(v[i][k+1]=='#')) + 1);
        else ret = min(ret , solve(i,k+2,off(mask,j,k+1) | ((1<<k+1))*(v[i][k+1]=='#')) + ((1-((mask>>k+1)&1))&(v[i][k+1]=='#')) + 1);
    }
    return ret;
}
void solve(){
    cin>>n>>m;
    v.resize(n);
    for(auto &i:v) cin>>i;
    memset(dp,-1,sizeof(dp));
    cout<<solve(0,0,0)<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int solve(int, int, int)':
Main.cpp:19:69: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   19 |     if(v[i][j] == '#') ret = min(ret , solve(i,j+1,mask|(1<<j)) + (1-(mask>>j)&1));
      |                                                                    ~^~~~~~~~~~
Main.cpp:24:79: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |         else if(k + 2 == m) ret = min(ret , solve(i+1,0,off(mask,j,m-1)|((1<<m-1))*(v[i][m-1]=='#')) + ((1-((mask>>k+1)&1))&(v[i][k+1]=='#')) + 1);
      |                                                                              ~^~
Main.cpp:24:117: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         else if(k + 2 == m) ret = min(ret , solve(i+1,0,off(mask,j,m-1)|((1<<m-1))*(v[i][m-1]=='#')) + ((1-((mask>>k+1)&1))&(v[i][k+1]=='#')) + 1);
      |                                                                                                                    ~^~
Main.cpp:25:66: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   25 |         else ret = min(ret , solve(i,k+2,off(mask,j,k+1) | ((1<<k+1))*(v[i][k+1]=='#')) + ((1-((mask>>k+1)&1))&(v[i][k+1]=='#')) + 1);
      |                                                                 ~^~
Main.cpp:25:104: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         else ret = min(ret , solve(i,k+2,off(mask,j,k+1) | ((1<<k+1))*(v[i][k+1]=='#')) + ((1-((mask>>k+1)&1))&(v[i][k+1]=='#')) + 1);
      |                                                                                                       ~^~

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