Submission #883941

# Submission time Handle Problem Language Result Execution time Memory
883941 2023-12-06T13:11:26 Z HossamHero7 Selotejp (COCI20_selotejp) C++14
0 / 110
9 ms 41684 KB
#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,k,m-1)) + 1);
        else if(k + 2 == m) ret = min(ret , solve(i+1,0,off(mask,k,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<<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

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,k,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,k,m-1)|((1<<m-1))*(v[i][m-1]=='#')) + ((1-((mask>>k+1)&1))&(v[i][k+1]=='#')) + 1);
      |                                                                                                                    ~^~
Main.cpp:25:64: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   25 |         else ret = min(ret , solve(i,k+2,off(mask,j,k) | ((1<<k+1))*(v[i][k+1]=='#')) + ((1-((mask>>k+1)&1))&(v[i][k+1]=='#')) + 1);
      |                                                               ~^~
Main.cpp:25:102: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         else ret = min(ret , solve(i,k+2,off(mask,j,k) | ((1<<k+1))*(v[i][k+1]=='#')) + ((1-((mask>>k+1)&1))&(v[i][k+1]=='#')) + 1);
      |                                                                                                     ~^~
# Verdict Execution time Memory Grader output
1 Correct 6 ms 40536 KB Output is correct
2 Incorrect 9 ms 41684 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 40592 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 40536 KB Output is correct
2 Incorrect 9 ms 41684 KB Output isn't correct
3 Halted 0 ms 0 KB -