oj.uz

Submission #753234

# Submission time Handle Problem Language Result Execution time Memory
753234 2023-06-04T22:30:09 Z lohacho L-triominoes (CEOI21_ltriominoes) C++14
10 / 100
 8000 ms 97684 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
 
const int NS = 13;
int way[(1 << NS) + 4][(1 << NS) + 4];
vector<int> vway[(1 << NS) + 4];
int dist[(1 << NS) + 4];
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int w, h, k;
    cin >> w >> h >> k;
    vector<pair<int, int>> a(k);
    for(int i = 0; i < k; ++i){
        cin >> a[i].first >> a[i].second;
        swap(a[i].first, a[i].second);
        --a[i].first, --a[i].second;
    }
    sort(a.begin(), a.end());
 
    for(int i = 0; i < (1 << w); ++i){
        auto dfs = [&](auto&&self, int x, int bt)->void{
            int now = (i >> x & 1);
            if(now){
                self(self, x + 1, bt);
                return;
            }
            if(x == w){
                way[i][bt] = 1;
                return;
            }
            int nxt = (i >> (x + 1) & 1);
            int btnow = (bt >> x & 1);
 
            if(x + 1 < w && !nxt && !btnow){
                self(self, x + 2, bt | 1 << x);
            }
            if(x + 1 < w && !nxt){
                self(self, x + 2, bt | 1 << (x + 1));
            }
            if(x + 1 < w && !btnow){
                self(self, x + 1, bt | 1 << x | 1 << (x + 1));
            }
            if(!btnow && x && !(bt >> (x - 1) & 1)){
                self(self, x + 1, bt | 1 << x | 1 << (x - 1));
            }
        };
        dfs(dfs, 0, 0);
        for(int j = 0; j < (1 << w); ++j){
            if(way[i][j]){
                vway[i].push_back(j);
            }
        }
    }
 
    vector<int> dp(1 << w);
    int p = 0, bt = 0;
    while(p < k && a[p].first == 0){
        bt |= (1 << a[p].second);
        ++p;
    }
    dp[bt] = 1;
    for(int i = 1; i < h; ++i){
        if(p < k){
            int nxt = a[p].first;
            int add = (nxt - 6 - i) / 6;
            if(add > 0) i += add * 6;
        }
        bt = 0;
        while(p < k && a[p].first == i){
            bt |= (1 << a[p].second);
            ++p;
        }
        vector<int> ndp(1 << w);
        for(int j = 0; j < (1 << w); ++j){
            if(!dp[j]) continue;
            for(auto&nxt:vway[j]){
                //cout << i << ' ' << j << ' ' << nxt << ' ' << bt << endl;
                if(!(nxt & bt)){
                    ndp[nxt | bt] = 1;
                }
            }
        }
        swap(dp, ndp);
    }
 
    if(dp[(1 << w) - 1]){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 528 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 1036 KB Output is correct
8 Correct 52 ms 37684 KB Output is correct
9 Correct 15 ms 14292 KB Output is correct
10 Correct 4 ms 3284 KB Output is correct
11 Correct 51 ms 37620 KB Output is correct
12 Correct 5 ms 6284 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 42 ms 37680 KB Output is correct
16 Correct 303 ms 97680 KB Output is correct
17 Correct 11 ms 6292 KB Output is correct
18 Correct 110 ms 37636 KB Output is correct
19 Correct 2 ms 952 KB Output is correct
20 Correct 258 ms 97612 KB Output is correct
21 Correct 96 ms 37784 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 2 ms 980 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 191 ms 97676 KB Output is correct
26 Correct 359 ms 97684 KB Output is correct
27 Correct 1 ms 596 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8016 ms 980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3419 ms 520 KB Output is correct
2 Execution timed out 8073 ms 468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 560 KB Output is correct
2 Correct 333 ms 564 KB Output is correct
3 Correct 1471 ms 632 KB Output is correct
4 Correct 1364 ms 624 KB Output is correct
5 Correct 651 ms 768 KB Output is correct
6 Correct 2132 ms 632 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 406 ms 624 KB Output is correct
10 Correct 134 ms 588 KB Output is correct
11 Correct 384 ms 632 KB Output is correct
12 Correct 3483 ms 764 KB Output is correct
13 Correct 96 ms 584 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 71 ms 596 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 603 ms 764 KB Output is correct
20 Execution timed out 8012 ms 724 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 1100 KB Output is correct
2 Correct 6263 ms 1024 KB Output is correct
3 Correct 385 ms 1660 KB Output is correct
4 Execution timed out 8022 ms 37712 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 528 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 1036 KB Output is correct
8 Correct 52 ms 37684 KB Output is correct
9 Correct 15 ms 14292 KB Output is correct
10 Correct 4 ms 3284 KB Output is correct
11 Correct 51 ms 37620 KB Output is correct
12 Correct 5 ms 6284 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 42 ms 37680 KB Output is correct
16 Correct 303 ms 97680 KB Output is correct
17 Correct 11 ms 6292 KB Output is correct
18 Correct 110 ms 37636 KB Output is correct
19 Correct 2 ms 952 KB Output is correct
20 Correct 258 ms 97612 KB Output is correct
21 Correct 96 ms 37784 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 2 ms 980 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 191 ms 97676 KB Output is correct
26 Correct 359 ms 97684 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Execution timed out 8016 ms 980 KB Time limit exceeded
29 Halted 0 ms 0 KB -