oj.uz

Submission #753232

# Submission time Handle Problem Language Result Execution time Memory
753232 2023-06-04T22:28:14 Z lohacho L-triominoes (CEOI21_ltriominoes) C++14
0 / 100
 8000 ms 49688 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 - 6 - 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 1 ms 468 KB Output is correct
2 Incorrect 1 ms 532 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 8050 ms 1040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3134 ms 520 KB Output is correct
2 Execution timed out 8053 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 211 ms 468 KB Output is correct
2 Correct 330 ms 580 KB Output is correct
3 Correct 1376 ms 636 KB Output is correct
4 Correct 1260 ms 716 KB Output is correct
5 Correct 592 ms 780 KB Output is correct
6 Correct 1998 ms 628 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 656 KB Output is correct
9 Correct 520 ms 648 KB Output is correct
10 Correct 133 ms 588 KB Output is correct
11 Correct 365 ms 656 KB Output is correct
12 Correct 3347 ms 780 KB Output is correct
13 Correct 105 ms 576 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 104 ms 640 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 656 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 789 ms 780 KB Output is correct
20 Execution timed out 8044 ms 788 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1414 ms 1108 KB Output is correct
2 Correct 5818 ms 1088 KB Output is correct
3 Correct 372 ms 1944 KB Output is correct
4 Execution timed out 8009 ms 49688 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 Incorrect 1 ms 532 KB Output isn't correct
3 Halted 0 ms 0 KB -