Submission #960968

#	Time	Username	Problem	Language	Result	Execution time	Memory
960968		LucaIlie	L-triominoes (CEOI21_ltriominoes)	C++17	10 / 100	8050 ms	288960 KiB

ltrominoes

#include <bits/stdc++.h>

using namespace std;

const int MAX_W = 13;
const int MAX_N = (1 << MAX_W);
map<int, int> conf;
bitset<MAX_N> adj[MAX_N];

bool hasBit( int mask, int i ) {
    return ((mask >> i) & 1);
}

int main() {
    int w, h, k;

    cin >> w >> h >> k;
    conf[0] = conf[h - 1] = 0;
    for ( int i = 0; i < k; i++ ) {
        int l, c;
        cin >> l >> c;
        l--;
        c--;
        conf[c] += (1 << l);
    }

    int n = (1 << w);
    for ( int mask = 0; mask < n; mask++ ) {
        vector<int> prvVec1 = { 0 }, prvVec2 = { 0 };
        for ( int i = 0; i < w; i++ ) {
            vector<int> vec;

            if ( hasBit( mask, i ) ) {
                for ( int m: prvVec1 )
                    vec.push_back( m );
            } else {
                for ( int m: prvVec1 ) {
                    if ( i >= 1 && !hasBit( m, i - 1 ) && !hasBit( m, i ) )
                        vec.push_back( m + (1 << (i - 1)) + (1 << i) );
                    if ( i <= w - 2 && !hasBit( m, i ) && !hasBit( m, i + 1 ) )
                        vec.push_back( m + (1 << i) + (1 << (i + 1)) );
                }

                if ( i >= 1 && !hasBit( mask, i - 1 ) ) {
                    for ( int m: prvVec2 ) {
                        if ( !hasBit( m, i - 1 ) )
                            vec.push_back( m + (1 << (i - 1)) );
                        if ( !hasBit( m, i ) )
                            vec.push_back( m + (1 << i) );
                    }
                }
            }

            prvVec2 = prvVec1;
            prvVec1 = vec;
        }


        for ( int m: prvVec1 )
            adj[mask][m] = 1;
    }

    bitset<MAX_N> pos;
    pos[conf[0]] = true;
    for ( int j = 1; j < h; j++ ) {
        bitset<MAX_N> newPos;
        for ( int m = 0; m < n; m++ ) {
            if ( pos[m] )
                newPos |= adj[m];
        }

        pos.reset();
        for ( int m = 0; m < n; m++ ) {
            if ( (conf[j] & m) == 0 )
                pos[conf[j] | m] = newPos[m];
        }
    }

    cout << (pos[n - 1] ? "YES\n" : "NO\n");

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20