Submission #1098778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098778		hiensumi	Selotejp (COCI20_selotejp)	C++14	35 / 110	127 ms	242788 KiB

Main

#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 (stderr)

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 / 35
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40