Submission #376676

#	Time	Username	Problem	Language	Result	Execution time	Memory
376676		lyc	Selotejp (COCI20_selotejp)	C++14	110 / 110	58 ms	40428 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 1000;
const int mxM = 10;

int N, M;
string G[mxN];
int dp[mxN+1][mxM][1<<mxM];

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

    cin >> N >> M;
    FOR(i,0,N-1){
        cin >> G[i];
    }

    RFOR(i,N-1,0){
        RFOR(j,M-1,0){
            FOR(x,0,(1<<M)-1){
                if (G[i][j] == '.') {
                    dp[i][j][x] = dp[i+(j+1)/M][(j+1)%M][x];
                } else {
                    // 1 v 0 h
                    dp[i][j][x] = min(
                        dp[i+(j+1)/M][(j+1)%M][x|(1<<j)] + (i==0 || G[i-1][j]=='.' || (x&(1<<j))==0),
                        dp[i+(j+1)/M][(j+1)%M][x&(~(1<<j))] + (j==0 || G[i][j-1]=='.' || (x&(1<<(j-1)))>0)
                    );
                }
                //TRACE(i _ j _ x _ dp[i][j][x]);
            }}}

    cout << dp[0][0][0] << '\n';
}

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