Submission #572079

#	Time	Username	Problem	Language	Result	Execution time	Memory
572079		gggkik	물탱크 (KOI18_watertank)	C++17	100 / 100	525 ms	44152 KiB

watertank

#include <bits/stdc++.h>
using namespace std;
int A[2020][2020], n, m, h;
int d[2010][2010], E[1010][1010][4];
int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 };
struct str {
    int x, y, d;
};
priority_queue<str> pq;
bool operator<(str i, str j) {
    return i.d > j.d;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> h;
    for (int i = 1; i <= n + 1; i++) {
        for (int j = 1; j <= m; j++) {
            d[i][j] = h;
            cin >> E[i][j][1];
            E[i - 1][j][0] = E[i][j][1];
        }
    }
    //for(int j = 1;j<=m;j++) cin >> E[n+1][j][0];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m+1; j++) {
            cin >> E[i][j][3];
            E[i][j - 1][2] = E[i][j][3];
        }
    }
    //cout << '\n';
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int edge = 1 << 30;
            for (int l = 0; l < 4; l++) {
                //printf("[%d] ", E[i][j][l]);
                int x = i + dx[l], y = j + dy[l];
                if (x == 0 || y == 0 || x == n + 1 || y == m + 1) {
                    if (E[i][j][l] != -1) {
                        edge = min(edge, E[i][j][l]);
                        //cout << "EDGE IS " << edge << ' ';
                    }
                }
                //else cout << x << ' ' << y << '\n';
            }
            if (edge != 1 << 30) {
               // printf("\n(%d %d) pushed %d\n", i, j, edge);
                d[i][j] = edge;
                pq.push({ i,j,edge });
            }
        }
    }
    // for(int i = 0;i<=2*n;i++){
    //     for(int j = 0;j<=2*m;j++)
    //         printf("%3d ",A[i][j]);
    //     cout << '\n';
    // }
    while (!pq.empty()) {
        str now = pq.top();
        //printf("%d %d : %d\n", now.x, now.y, now.d);
        pq.pop();
        if (d[now.x][now.y] < now.d) continue;
        for (int i = 0; i < 4; i++) {
            if (E[now.x][now.y][i] == -1) continue;
            int ax = now.x + dx[i], ay = now.y + dy[i];
            if (ax<1 || ay<1 || ax>n || ay>m) continue;
            int cost = max(now.d, E[now.x][now.y][i]);
            
            if (d[ax][ay] > cost) {
                //printf("(%d %d) -> (%d %d)[%d]\n", now.x, now.y, ax, ay,E[now.x][now.y][i]);
                d[ax][ay] = cost;
                pq.push({ ax,ay,cost });
            }
        }
    }
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
                sum += d[i][j];
        }
    }
    
    cout << sum;
}

• Subtask 1: 6 / 6
• Subtask 2: 18 / 18
• Subtask 3: 15 / 15
• Subtask 4: 21 / 21
• Subtask 5: 40 / 40