Submission #101989

#	Time	Username	Problem	Language	Result	Execution time	Memory
101989		lobo_prix	물탱크 (KOI18_watertank)	C++17	100 / 100	768 ms	32300 KiB

watertank

#ifndef DEBUG
  #pragma GCC optimize ("Ofast")
#endif
#include <bits/stdc++.h>

//Syntax Sugars
using namespace std;
using f64 = double;
using i8=char;using i16=short;using i32=int;using i64=long long;
using u8=unsigned char;using u16=unsigned short;using u32=unsigned;using u64=unsigned long long;
const f64 pi=acos(-1);
const f64 eps=1e-12;
const i32 prime=i32(2e9 + 11);
i32 mod=i32(1e9 + 7);
template<typename T> T inf() { return numeric_limits<T>::max() / 2; }
#define forh(var, s, e) for(int var=s; (int)s<=var && var<(int)e; ++var)//for: half-opened range
#define forhi(var, s, e) for(int var=e-1; (int)s<=var && var<(int)e; --var)//inversion
#define forho(var, s, e) int var=s; for(; (int)s<=var && var<(int)e; ++var)//out declaration
#define forhoi(var, s, e) int var=e-1; for(; (int)s<=var && var<(int)e; --var)
#define forc(var, s, e) for(int var=s; (int)s<=var && var<=(int)e; ++var)//for: closed range
#define forci(var, s, e) for(int var=e; (int)s<=var && var<=(int)e; --var)//inversion
#define forco(var, s, e) int var=s; for(; (int)s<=var && var<=(int)e; ++var)//out declaration
#define forcoi(var, s, e) int var=e; for(; (int)s<=var && var<=(int)e; --var)

//Extensions
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;

//Settings
#define endl '\n'//do not use when solving interactive problem!!!

struct State{
  int val, y, x;
  bool operator<(const State& r)const{
    return val>r.val;
  }
};

int n,m,h;
int arr1[1010][1010];
int arr2[1010][1010];
int dist[1010][1010];

bool safe(int y, int x){return 0<=y&&y<n&&0<=x&&x<m;}

int main(){
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cout<<fixed<<setprecision(11);
  srand((u32)time(0));
  
  cin>>n>>m>>h;
  forh(i,0,n+1)
    forh(j,0,m)
      cin>>arr1[i][j];
  forh(i,0,n)
    forh(j,0,m+1)
      cin>>arr2[i][j];
  priority_queue<State> pq;
  forh(i,0,n)
    forh(j,0,m)
      dist[i][j]=h;
  forh(j,0,m){
    if(arr1[0][j]!=-1)
      pq.push({dist[0][j]=min(dist[0][j], arr1[0][j]), 0, j});
    if(arr1[n][j]!=-1)
      pq.push({dist[n-1][j]=min(dist[n-1][j], arr1[n][j]), n-1, j});
  }
  forh(i,0,n){
    if(arr2[i][0]!=-1)
      pq.push({dist[i][0]=min(dist[i][0], arr2[i][0]), i, 0});
    if(arr2[i][m]!=-1)
      pq.push({dist[i][m-1]=min(dist[i][m-1], arr2[i][m]), i, m-1});
  }
  while(pq.size()){
    auto cur=pq.top();
    pq.pop();
    if(cur.val<dist[cur.y][cur.x])
      continue;
    int ny,nx;
    ny=cur.y+1, nx=cur.x;
    if(safe(ny,nx)&&arr1[ny][nx]!=-1&&dist[ny][nx]>max(cur.val, arr1[ny][nx]))
      pq.push({dist[ny][nx]=max(cur.val, arr1[ny][nx]), ny, nx});
    ny=cur.y, nx=cur.x+1;
    if(safe(ny,nx)&&arr2[ny][nx]!=-1&&dist[ny][nx]>max(cur.val, arr2[ny][nx]))
      pq.push({dist[ny][nx]=max(cur.val, arr2[ny][nx]), ny, nx});
    ny=cur.y-1, nx=cur.x;
    if(safe(ny,nx)&&arr1[ny+1][nx]!=-1&&dist[ny][nx]>max(cur.val, arr1[ny+1][nx]))
      pq.push({dist[ny][nx]=max(cur.val, arr1[ny+1][nx]), ny, nx});
    ny=cur.y, nx=cur.x-1;
    if(safe(ny,nx)&&arr2[ny][nx+1]!=-1&&dist[ny][nx]>max(cur.val, arr2[ny][nx+1]))
      pq.push({dist[ny][nx]=max(cur.val, arr2[ny][nx+1]), ny, nx});
  }
  i64 ans=0;
  forh(i,0,n)
    forh(j,0,m)
      ans+=dist[i][j];
  cout<<ans<<endl;

  return 0;
}

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