oj.uz

Submission #1098778

# Submission time Handle Problem Language Result Execution time Memory
1098778 2024-10-10T00:26:56 Z hiensumi Selotejp (COCI20_selotejp) C++14
35 / 110
 127 ms 242788 KB 
#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i = (int) (a); i <= (int) (b); i++)
#define fok(i,a,b) for(int i = (int) (a); i >= (int) (b); i--)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define el '\n'
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define mask(a) (1LL<<(a))
#define BIT(msk,i) (msk>>(i)&1LL)
using namespace std;
template <class T> bool mini(T &a, T b){ return (a > (b)) ? a = (b), 1 : 0; }
template <class T> bool maxi(T &a, T b){ return (a < (b)) ? a = (b), 1 : 0; }
#define name "selotejp"

int n, m;

char a[1005][15];

int dp[1005][15][mask(12)];

int off(int msk, int pos){
    if(!BIT(msk, pos)) return msk;
    return msk ^ mask(pos);
}
int on(int msk, int pos){
    if(BIT(msk, pos)) return msk;
    return msk ^ mask(pos);
}

int f(int i, int j, int msk, bool from_left){
    if(i == n + 1) return 0;
    if(j == m + 1) return f(i + 1, 1, msk, 0);

    int &res = dp[i][j][msk];
    if(~res) return res;

    res = 1e9;

    int up = BIT(msk, j);

    if((up or from_left) and a[i][j] == '#') return res = f(i, j + 1, msk, from_left);
    if(up == 0 and from_left == 0 and a[i][j] == '#') return res = min(f(i,j+1,on(msk,j), 0), f(i,j+1,off(msk,j),1)) + 1;

    if(a[i][j] == '.') return res = f(i, j + 1, off(msk, j), 0);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;

    fod(i,1,n) fod(j,1,m){
         cin >> a[i][j];
    }

    memset(dp, -1, sizeof dp);

    cout << f(1,1,0,0);

    return 0;
}

Compilation message

Main.cpp: In function 'int f(int, int, int, bool)':
Main.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 242004 KB Output is correct
2 Correct 100 ms 242768 KB Output is correct
3 Correct 120 ms 242500 KB Output is correct
4 Correct 104 ms 242676 KB Output is correct
5 Correct 107 ms 242772 KB Output is correct
6 Correct 105 ms 242768 KB Output is correct
7 Correct 103 ms 242788 KB Output is correct
8 Correct 114 ms 242768 KB Output is correct
9 Correct 119 ms 242768 KB Output is correct
10 Correct 122 ms 242768 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 242004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 242004 KB Output is correct
2 Correct 100 ms 242768 KB Output is correct
3 Correct 120 ms 242500 KB Output is correct
4 Correct 104 ms 242676 KB Output is correct
5 Correct 107 ms 242772 KB Output is correct
6 Correct 105 ms 242768 KB Output is correct
7 Correct 103 ms 242788 KB Output is correct
8 Correct 114 ms 242768 KB Output is correct
9 Correct 119 ms 242768 KB Output is correct
10 Correct 122 ms 242768 KB Output is correct
11 Incorrect 127 ms 242004 KB Output isn't correct
12 Halted 0 ms 0 KB -