oj.uz

Submission #101983

# Submission time Handle Problem Language Result Execution time Memory
101983 2019-03-21T08:54:34 Z lobo_prix None (KOI18_watertank) C++17
15 / 100
 250 ms 22528 KB 
#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]=arr1[0][j], 0, j});
    if(arr1[n][j]!=-1)
      pq.push({dist[n-1][j]=arr1[n][j], n-1, j});
  }
  forh(i,0,n){
    if(arr2[i][0]!=-1)
      pq.push({dist[i][0]=arr2[i][0], i, 0});
    if(arr2[i][m]!=-1)
      pq.push({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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 18168 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 122 ms 16164 KB Output is correct
4 Correct 140 ms 16220 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 232 ms 17332 KB Output is correct
7 Correct 123 ms 16448 KB Output is correct
8 Correct 250 ms 22528 KB Output is correct
9 Correct 128 ms 15864 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 242 ms 18032 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1052 KB Output isn't correct
2 Halted 0 ms 0 KB -