oj.uz

Submission #778108

# Submission time Handle Problem Language Result Execution time Memory
778108 2023-07-10T06:24:01 Z 이동현(#9997) Wall (CEOI14_wall) C++17
30 / 100
 1088 ms 37112 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

int n, m;
int a[404][404], v[404][404], h[404][404];
long long dist[44][44][1024];
int chk[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);
            }
        }
        return rv;
    };

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

        if(y + 1 <= m + 1 && nd + h[x][y] < dist[x][y + 1][bt]){
            dist[x][y + 1][bt] = nd + h[x][y];
            pq.push({-(nd + h[x][y]), x, y + 1, bt});
        }
        if(y - 1 >= 1 && nd + h[x][y - 1] < dist[x][y - 1][bt]){
            dist[x][y - 1][bt] = nd + h[x][y - 1];
            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]){
                dist[x + 1][y][bt | nbt] = nd + v[x][y];
                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]){
                dist[x - 1][y][bt - nbt] = nd + v[x - 1][y];
                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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15876 KB Output is correct
2 Correct 9 ms 15960 KB Output is correct
3 Correct 6 ms 15908 KB Output is correct
4 Correct 6 ms 15872 KB Output is correct
5 Correct 6 ms 15828 KB Output is correct
6 Correct 8 ms 16024 KB Output is correct
7 Correct 225 ms 22048 KB Output is correct
8 Correct 7 ms 16048 KB Output is correct
9 Correct 7 ms 16004 KB Output is correct
10 Correct 7 ms 16084 KB Output is correct
11 Correct 690 ms 28316 KB Output is correct
12 Correct 39 ms 16232 KB Output is correct
13 Correct 26 ms 18104 KB Output is correct
14 Correct 962 ms 25200 KB Output is correct
15 Correct 8 ms 16084 KB Output is correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 32284 KB Execution killed with signal 11
2 Incorrect 1088 ms 19112 KB Output isn't correct
3 Incorrect 963 ms 28840 KB Output isn't correct
4 Correct 7 ms 16044 KB Output is correct
5 Runtime error 22 ms 32724 KB Execution killed with signal 11
6 Runtime error 23 ms 32796 KB Execution killed with signal 11
7 Runtime error 22 ms 32384 KB Execution killed with signal 11
8 Incorrect 930 ms 18348 KB Output isn't correct
9 Correct 9 ms 16468 KB Output is correct
10 Incorrect 7 ms 16112 KB Output isn't correct
11 Runtime error 23 ms 32368 KB Execution killed with signal 11
12 Runtime error 20 ms 32500 KB Execution killed with signal 11
13 Runtime error 20 ms 32364 KB Execution killed with signal 11
14 Correct 934 ms 18288 KB Output is correct
15 Correct 22 ms 18264 KB Output is correct
16 Incorrect 7 ms 16044 KB Output isn't correct
17 Runtime error 20 ms 32348 KB Execution killed with signal 11
18 Runtime error 21 ms 32268 KB Execution killed with signal 11

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 19820 KB Output isn't correct
2 Incorrect 15 ms 16668 KB Output isn't correct
3 Incorrect 29 ms 17084 KB Output isn't correct
4 Incorrect 22 ms 16932 KB Output isn't correct
5 Runtime error 47 ms 37112 KB Execution killed with signal 11
6 Runtime error 91 ms 34920 KB Execution killed with signal 11
7 Runtime error 41 ms 35848 KB Execution killed with signal 11
8 Incorrect 20 ms 17260 KB Output isn't correct
9 Runtime error 34 ms 34932 KB Execution killed with signal 11
10 Incorrect 24 ms 17336 KB Output isn't correct
11 Incorrect 32 ms 17336 KB Output isn't correct
12 Runtime error 30 ms 34252 KB Execution killed with signal 11
13 Incorrect 45 ms 17408 KB Output isn't correct
14 Runtime error 42 ms 36208 KB Execution killed with signal 11
15 Incorrect 29 ms 17744 KB Output isn't correct
16 Runtime error 47 ms 35816 KB Execution killed with signal 11
17 Incorrect 33 ms 17784 KB Output isn't correct
18 Incorrect 46 ms 17700 KB Output isn't correct
19 Runtime error 59 ms 35968 KB Execution killed with signal 11
20 Runtime error 63 ms 36232 KB Execution killed with signal 11