oj.uz

Submission #778100

# Submission time Handle Problem Language Result Execution time Memory
778100 2023-07-10T06:20:00 Z 이동현(#9997) Wall (CEOI14_wall) C++17
20 / 100
 2000 ms 40028 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

int n, m;
int a[404][404], v[404][404], h[404][404];
int dist[44][44][1024];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    vector<vector<int>> pos;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> a[i][j];
            if(a[i][j]){
                pos.push_back({i, j});
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m + 1; ++j){
            cin >> v[i][j];
        }
    }
    for(int i = 1; i <= n + 1; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> h[i][j];
        }
    }

    for(int i = 0; i < 44; ++i){
        for(int j = 0; j < 44; ++j){
            for(int k = 0; k < 1024; ++k){
                dist[i][j][k] = (int)1e18;
            }
        }
    }

    auto get = [&](int x, int y){
        int rv = 0;
        for(int i = 0; i < (int)pos.size(); ++i){
            if(pos[i][0] == x && pos[i][1] <= y){
                rv |= (1 << i);
            }
        }
        // cout << "GET " << x << ' ' << y << ' ' << rv << endl;
        return rv;
    };

    priority_queue<vector<int>> pq;
    pq.push({0, 1, 1, 0});
    while(!pq.empty()){
        int nd = -pq.top()[0], x = pq.top()[1], y = pq.top()[2], bt = pq.top()[3];
        pq.pop();
        if(nd >= dist[x][y][bt]){
            continue;
        }
        dist[x][y][bt] = nd;

        if(y + 1 <= m + 1 && nd + h[x][y] < dist[x][y + 1][bt]){
            pq.push({-(nd + h[x][y]), x, y + 1, bt});
        }
        if(y - 1 >= 1 && nd + h[x][y - 1] < dist[x][y - 1][bt]){
            pq.push({-(nd + h[x][y - 1]), x, y - 1, bt});
        }
        if(x + 1 <= n + 1){
            int nbt = get(x, y - 1);
            if(!(bt & nbt) && nd + v[x][y] < dist[x + 1][y][bt | nbt]){
                pq.push({-(nd + v[x][y]), x + 1, y, bt | nbt});
            }
        }
        if(x - 1 >= 1){
            int nbt = get(x - 1, y - 1);
            if((bt & nbt) == nbt && nd + v[x - 1][y] < dist[x - 1][y][bt - nbt]){
                pq.push({-(nd + v[x - 1][y]), x - 1, y, bt - nbt});
            }
        }
    }

    cout << dist[1][1][(1 << (int)pos.size()) - 1];
    
    return 0;
}

Subtask #1
20.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15988 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 9 ms 16212 KB Output is correct
7 Correct 695 ms 24344 KB Output is correct
8 Correct 31 ms 16596 KB Output is correct
9 Correct 8 ms 16084 KB Output is correct
10 Correct 8 ms 16340 KB Output is correct
11 Correct 1234 ms 28516 KB Output is correct
12 Correct 51 ms 16468 KB Output is correct
13 Correct 573 ms 23132 KB Output is correct
14 Execution timed out 2073 ms 32888 KB Time limit exceeded
15 Correct 10 ms 16384 KB Output is correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 32680 KB Execution killed with signal 11
2 Incorrect 1541 ms 20072 KB Output isn't correct
3 Incorrect 1784 ms 33624 KB Output isn't correct
4 Correct 13 ms 16596 KB Output is correct
5 Runtime error 23 ms 33284 KB Execution killed with signal 11
6 Runtime error 24 ms 33440 KB Execution killed with signal 11
7 Runtime error 19 ms 32652 KB Execution killed with signal 11
8 Incorrect 1356 ms 19996 KB Output isn't correct
9 Correct 247 ms 20132 KB Output is correct
10 Incorrect 25 ms 16664 KB Output isn't correct
11 Runtime error 21 ms 32724 KB Execution killed with signal 11
12 Runtime error 21 ms 32852 KB Execution killed with signal 11
13 Runtime error 20 ms 32740 KB Execution killed with signal 11
14 Correct 1451 ms 20024 KB Output is correct
15 Correct 286 ms 23348 KB Output is correct
16 Incorrect 16 ms 16480 KB Output isn't correct
17 Runtime error 21 ms 32760 KB Execution killed with signal 11
18 Runtime error 23 ms 32748 KB Execution killed with signal 11

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 468 ms 30080 KB Output isn't correct
2 Incorrect 12 ms 17492 KB Output isn't correct
3 Incorrect 38 ms 18388 KB Output isn't correct
4 Incorrect 25 ms 17860 KB Output isn't correct
5 Runtime error 48 ms 39956 KB Execution killed with signal 11
6 Runtime error 97 ms 37652 KB Execution killed with signal 11
7 Runtime error 42 ms 38860 KB Execution killed with signal 11
8 Incorrect 20 ms 18784 KB Output isn't correct
9 Runtime error 44 ms 37800 KB Execution killed with signal 11
10 Incorrect 24 ms 18744 KB Output isn't correct
11 Incorrect 27 ms 18888 KB Output isn't correct
12 Runtime error 28 ms 36128 KB Execution killed with signal 11
13 Incorrect 29 ms 18772 KB Output isn't correct
14 Runtime error 49 ms 39956 KB Execution killed with signal 11
15 Incorrect 28 ms 19660 KB Output isn't correct
16 Runtime error 47 ms 39644 KB Execution killed with signal 11
17 Incorrect 33 ms 19600 KB Output isn't correct
18 Incorrect 36 ms 19648 KB Output isn't correct
19 Runtime error 46 ms 39804 KB Execution killed with signal 11
20 Runtime error 60 ms 40028 KB Execution killed with signal 11