Submission #1098783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098783		hiensumi	Selotejp (COCI20_selotejp)	C++14	110 / 110	192 ms	122304 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(11)];

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(a[i][j] == '.') return res = f(i,j+1,off(msk,j),0);

    if(up) mini(res, f(i,j+1,msk,0));
    else mini(res, f(i,j+1,on(msk,j),0) + 1);
    if(from_left) mini(res, f(i,j+1,off(msk,j),1));
    else mini(res, f(i,j+1,off(msk,j),1) + 1);

    return res;
}

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;
}

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