oj.uz

Submission #883944

# Submission time Handle Problem Language Result Execution time Memory
883944 2023-12-06T13:18:10 Z HossamHero7 Selotejp (COCI20_selotejp) C++14
110 / 110
 243 ms 41976 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,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

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.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 40540 KB Output is correct
2 Correct 8 ms 41868 KB Output is correct
3 Correct 8 ms 41564 KB Output is correct
4 Correct 8 ms 41652 KB Output is correct
5 Correct 9 ms 41820 KB Output is correct
6 Correct 10 ms 41948 KB Output is correct
7 Correct 9 ms 41820 KB Output is correct
8 Correct 7 ms 41820 KB Output is correct
9 Correct 8 ms 41820 KB Output is correct
10 Correct 23 ms 41976 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 40540 KB Output is correct
2 Correct 6 ms 40540 KB Output is correct
3 Correct 5 ms 40640 KB Output is correct
4 Correct 6 ms 40540 KB Output is correct
5 Correct 5 ms 40540 KB Output is correct
6 Correct 5 ms 40552 KB Output is correct
7 Correct 5 ms 40740 KB Output is correct
8 Correct 5 ms 40536 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 40540 KB Output is correct
2 Correct 8 ms 41868 KB Output is correct
3 Correct 8 ms 41564 KB Output is correct
4 Correct 8 ms 41652 KB Output is correct
5 Correct 9 ms 41820 KB Output is correct
6 Correct 10 ms 41948 KB Output is correct
7 Correct 9 ms 41820 KB Output is correct
8 Correct 7 ms 41820 KB Output is correct
9 Correct 8 ms 41820 KB Output is correct
10 Correct 23 ms 41976 KB Output is correct
11 Correct 5 ms 40540 KB Output is correct
12 Correct 6 ms 40540 KB Output is correct
13 Correct 5 ms 40640 KB Output is correct
14 Correct 6 ms 40540 KB Output is correct
15 Correct 5 ms 40540 KB Output is correct
16 Correct 5 ms 40552 KB Output is correct
17 Correct 5 ms 40740 KB Output is correct
18 Correct 5 ms 40536 KB Output is correct
19 Correct 6 ms 41308 KB Output is correct
20 Correct 9 ms 41572 KB Output is correct
21 Correct 11 ms 41652 KB Output is correct
22 Correct 6 ms 41896 KB Output is correct
23 Correct 6 ms 41820 KB Output is correct
24 Correct 8 ms 41820 KB Output is correct
25 Correct 14 ms 41916 KB Output is correct
26 Correct 48 ms 41820 KB Output is correct
27 Correct 125 ms 41888 KB Output is correct
28 Correct 243 ms 41928 KB Output is correct