oj.uz

Submission #752856

# Submission time Handle Problem Language Result Execution time Memory
752856 2023-06-04T04:54:38 Z lohacho L-triominoes (CEOI21_ltriominoes) C++14
0 / 100
 8000 ms 49596 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
#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 - 13 - i) / 3;
            if(add > 0) i += add * 3;
        }
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Incorrect 0 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8092 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 3152 ms 516 KB Output is correct
2 Execution timed out 8069 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 215 ms 580 KB Output is correct
2 Correct 326 ms 568 KB Output is correct
3 Correct 1412 ms 636 KB Output is correct
4 Correct 1290 ms 632 KB Output is correct
5 Correct 590 ms 784 KB Output is correct
6 Correct 2000 ms 636 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 500 ms 640 KB Output is correct
10 Correct 127 ms 576 KB Output is correct
11 Correct 339 ms 648 KB Output is correct
12 Correct 3224 ms 780 KB Output is correct
13 Correct 92 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 89 ms 644 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 664 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 730 ms 792 KB Output is correct
20 Execution timed out 8029 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 1439 ms 1084 KB Output is correct
2 Correct 5715 ms 1088 KB Output is correct
3 Correct 368 ms 1940 KB Output is correct
4 Execution timed out 8034 ms 49596 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Incorrect 0 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -