Submission #571885

#	Time	Username	Problem	Language	Result	Execution time	Memory
571885		gggkik	물탱크 (KOI18_watertank)	C++14	0 / 100	3051 ms	25880 KiB

watertank

#include <bits/stdc++.h>
using namespace std;
int A[2020][2020], n, m, h;
int d[1010][1010];
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 = 0;i<=2*n;i++){
        for(int j = 0;j<=2*m;j++){
            if(!(j%2 || i%2)) A[i][j] = -1;
            d[i][j] = 1<<30;
            if(i%2 == j%2 && i%2 == 1) d[i][j] = h;
            if(i==0 || j == 0 || i == 2*n || j == 2*m) {
                if(A[i][j]==0) A[i][j] = -1;
            } 
        }
    }
    for(int i = 0;i<m;i++){
        for(int j = 0;j<n+1;j++){
            cin >> A[i*2][j*2+1];
        }
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m+1;j++){
            cin >> A[i*2+1][j*2];
        }
    }
    for(int i = 0;i<=2*n;i++){
        for(int j = 0;j<=2*m;j++){
            if(i%2==j%2 && i%2==1){
                if(A[i][j]==-1) continue;
                int mo = 1<<30;
                //printf("[%d %d]\n",i,j);
                for(int l = 0;l<4;l++){
                    if(i+dx[l] == 0 || j+dy[l] == 0 || i+dx[l] == 2*n || j+dy[l] == 2*m){
                        if(A[i+dx[l]][j+dy[l]]!=-1) {
                            mo = min(A[i+dx[l]][j+dy[l]],mo);
                            //printf("*%d,%d*V(%d)",i+dx[l],j+dy[l],A[i+dx[l]][j+dy[l]]);
                        }
                    }
                }
                if(mo!=1<<30)
                if(d[i][j]>A[i][j]-1) {
                    //printf("{%d %d}\n",i,j);
                    //printf("(%d)\n",mo);
                    pq.push({i,j,mo});
                    d[i][j] = mo;
                }
            }
        }
    }
    // 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();
        pq.pop();
        for(int i = 0;i<4;i++){
            int ax = now.x + dx[i]*2, ay = now.y + dy[i]*2;
            if(ax<0 || ay<0 || ax>2*n || ay>2*m) continue;
            if(A[now.x + dx[i]][now.y + dy[i]]==-1) continue;
            int cost = max(now.d,A[now.x + dx[i]][now.y + dy[i]]);
            if(d[ax][ay] > cost) {
                d[ax][ay] = cost;
                pq.push({ax,ay,cost});
            }
        }
    }
    long long sum = 0;
    for(int i = 0;i<=2*n;i++){
        for(int j = 0;j<=2*m;j++) {
            if(d[i][j]!=1<<30){
                sum += d[i][j];
                //cout << d[i][j] << ' ';
            }
            //else cout << "W ";
        }
        //cout << '\n';
    }
    cout << sum;
}

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