oj.uz

Submission #778371

# Submission time Handle Problem Language Result Execution time Memory
778371 2023-07-10T08:57:24 Z 이동현(#9997) Wall (CEOI14_wall) C++17
0 / 100
 2000 ms 102636 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][44][44][2];
int chk[44][44][44][44][2];

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 < 44; ++k){
                for(int k2 = 0; k2 < 44; ++k2){
                    dist[i][j][k][k2][0] = dist[i][j][k][k2][1] = (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;
            }
        }
        return rv;
    };
    auto get2 = [&](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;
            }
        }
        return rv;
    };

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

        // cout << x << ' ' << y << ' ' << r << ' ' << l << ' ' << bt << ' ' << nd << endl;
        if(x == 1 && y == 1 && bt == 1 && r == (int)pos.size() && l == (int)pos.size()) break;

        if(y + 1 <= m + 1 && nd + h[x][y] < dist[x][y + 1][r][l][bt]){
            dist[x][y + 1][r][l][bt] = nd + h[x][y];
            pq.push({-(nd + h[x][y]), x, y + 1, r, l, bt});
        }
        if(y - 1 >= 1 && nd + h[x][y - 1] < dist[x][y - 1][r][l][bt]){
            dist[x][y - 1][r][l][bt] = nd + h[x][y - 1];
            pq.push({-(nd + h[x][y - 1]), x, y - 1, r, l, bt});
        }
        if(x + 1 <= n + 1){
            int bt1 = get(x, y - 1);
            int bt2 = get2(x, y - 1);
            int nbt = bt;
            if(!l && r + bt1 == n) nbt = 1;
            if(r + bt1 <= (int)pos.size() && l - bt2 >= 0 && nd + v[x][y] < dist[x + 1][y][r + bt1][l - bt2][nbt]){
                dist[x + 1][y][r + bt1][l - bt2][nbt] = nd + v[x][y];
                pq.push({-(nd + v[x][y]), x + 1, y, r + bt1, l - bt2, nbt});
            }
        }
        if(x - 1 >= 1){
            int bt1 = get(x - 1, y - 1);
            int bt2 = get2(x - 1, y - 1);
            if(r - bt1 >= 0 && l + bt2 <= (int)pos.size() && nd + v[x - 1][y] < dist[x - 1][y][r - bt1][l + bt2][bt]){
                dist[x - 1][y][r - bt1][l + bt2][bt] = nd + v[x - 1][y];
                pq.push({-(nd + v[x - 1][y]), x - 1, y, r - bt1, l + bt2, bt});
            }
        }
    }

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

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 59476 KB Output isn't correct
2 Incorrect 24 ms 59504 KB Output isn't correct
3 Incorrect 24 ms 59552 KB Output isn't correct
4 Incorrect 25 ms 59596 KB Output isn't correct
5 Incorrect 24 ms 59580 KB Output isn't correct
6 Incorrect 27 ms 63172 KB Output isn't correct
7 Incorrect 28 ms 63568 KB Output isn't correct
8 Incorrect 27 ms 63436 KB Output isn't correct
9 Incorrect 25 ms 61716 KB Output isn't correct
10 Incorrect 27 ms 62944 KB Output isn't correct
11 Incorrect 38 ms 66064 KB Output isn't correct
12 Incorrect 37 ms 66500 KB Output isn't correct
13 Incorrect 30 ms 66636 KB Output isn't correct
14 Incorrect 31 ms 67412 KB Output isn't correct
15 Incorrect 27 ms 64204 KB Output isn't correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 80624 KB Output isn't correct
2 Incorrect 38 ms 68856 KB Output isn't correct
3 Incorrect 29 ms 66852 KB Output isn't correct
4 Incorrect 28 ms 66052 KB Output isn't correct
5 Incorrect 53 ms 75072 KB Output isn't correct
6 Incorrect 47 ms 72884 KB Output isn't correct
7 Incorrect 48 ms 75616 KB Output isn't correct
8 Incorrect 29 ms 68652 KB Output isn't correct
9 Incorrect 24 ms 66252 KB Output isn't correct
10 Incorrect 26 ms 66268 KB Output isn't correct
11 Incorrect 58 ms 76744 KB Output isn't correct
12 Incorrect 45 ms 70784 KB Output isn't correct
13 Incorrect 61 ms 78712 KB Output isn't correct
14 Incorrect 27 ms 68512 KB Output isn't correct
15 Incorrect 24 ms 66504 KB Output isn't correct
16 Incorrect 23 ms 66516 KB Output isn't correct
17 Incorrect 47 ms 75912 KB Output isn't correct
18 Incorrect 33 ms 71124 KB Output isn't correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 304 ms 92328 KB Output isn't correct
2 Incorrect 42 ms 73228 KB Output isn't correct
3 Incorrect 50 ms 69484 KB Output isn't correct
4 Incorrect 51 ms 75832 KB Output isn't correct
5 Execution timed out 2083 ms 73716 KB Time limit exceeded
6 Execution timed out 2063 ms 95848 KB Time limit exceeded
7 Incorrect 1392 ms 97764 KB Output isn't correct
8 Incorrect 55 ms 76000 KB Output isn't correct
9 Incorrect 506 ms 94796 KB Output isn't correct
10 Incorrect 54 ms 75212 KB Output isn't correct
11 Incorrect 86 ms 81828 KB Output isn't correct
12 Execution timed out 2098 ms 90444 KB Time limit exceeded
13 Execution timed out 2065 ms 92476 KB Time limit exceeded
14 Execution timed out 2075 ms 91036 KB Time limit exceeded
15 Incorrect 64 ms 76688 KB Output isn't correct
16 Incorrect 1234 ms 101484 KB Output isn't correct
17 Incorrect 68 ms 77728 KB Output isn't correct
18 Incorrect 113 ms 91728 KB Output isn't correct
19 Execution timed out 2088 ms 102636 KB Time limit exceeded
20 Execution timed out 2081 ms 90628 KB Time limit exceeded