제출 #1256043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256043		comgaTramAnh	웜뱃 (IOI13_wombats)	C++20	18 / 100	660 ms	20636 KiB

wombats

#include <bits/stdc++.h> 
#include "wombats.h"
using namespace std;
long long sum = 0LL; 
int h[5000][200];
int v[5000][200]; 
int f[5000][200]; 
int ans[2][2]; 
int n, m; 
void init(int R, int C, int H[5000][200], int V[5000][200]) {
  n = R;
  m = C; 
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      h[i][j] = H[i][j];
      v[i][j] = V[i][j];
    }
  }  
}
void dijkstra(int u, int c) {
  const int inf = 1000000007; 
  for (int i = 0; i < n; i++) {
    f[i][0] = f[i][1] = inf; 
  }
  priority_queue <tuple <int, int, int>, vector <tuple <int, int, int>>, greater <tuple <int, int, int>>> pq; 
  f[0][c] = 0;
  pq.push(make_tuple(f[0][c], 0, c)); 
  while (pq.empty() == false) {
    tuple <int, int, int> element = pq.top();
    pq.pop(); 
    int dist = get <0>(element);
    int i = get <1>(element);
    int j = get <2>(element);
    if (f[i][j] != dist) {
      continue; 
    }
    if (j > 0) {
      if (f[i][j - 1] > f[i][j] + h[i][j - 1]) {
        f[i][j - 1] = f[i][j] + h[i][j - 1]; 
        pq.push(make_tuple(f[i][j - 1], i, j - 1)); 
      }
    }    
    if (j < m - 1) {
      if (f[i][j + 1] > f[i][j] + h[i][j]) {
        f[i][j + 1] = f[i][j] + h[i][j]; 
        pq.push(make_tuple(f[i][j + 1], i, j + 1)); 
      }
    }
    if (i < n - 1) {
      if (f[i + 1][j] > f[i][j] + v[i][j]) {
        f[i + 1][j] = f[i][j] + v[i][j]; 
        pq.push(make_tuple(f[i + 1][j], i + 1, j)); 
      }
    } 
  }
  ans[c][0] = min(ans[c][0], f[n - 1][0]);
  ans[c][1] = min(ans[c][1], f[n - 1][1]);
}
void changeH(int P, int Q, int W) {
  const int inf = 1000000007; 
  h[P][Q] = W;   
  ans[0][0] = ans[0][1] = ans[1][0] = ans[1][1] = inf;
  dijkstra(0, 0);
  dijkstra(0, 1); 
}
void changeV(int P, int Q, int W) {
  const int inf = 1000000007; 
  v[P][Q] = W;   
  ans[0][0] = ans[0][1] = ans[1][0] = ans[1][1] = inf;
  dijkstra(0, 0);
  dijkstra(0, 1);   
}
int escape(int V1, int V2) {
  return ans[V1][V2];    
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24