제출 #1260534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260534		repmann	웜뱃 (IOI13_wombats)	C++20	55 / 100	20101 ms	309896 KiB

wombats

#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
mt19937_64 rng(1);
int R, C;
int sz, I[200];
int H[5000][200], V[5000][200], DP[75][5000][200];
int temp[200];
inline void doDP(int u, int row = 0)
{
  int index = I[u];
  if(!row)
  {
    DP[index][0][u] = 0;
    for(int i = u - 1; i >= 0; i--) DP[index][0][i] = DP[index][0][i + 1] + H[0][i];
    if(u < (C - 1)) for(int i = u + 1; i < C; i++) DP[index][0][i] = DP[index][0][i - 1] + H[0][i - 1];
  }
  for(int i = row + !row; i < R; i++)
  {
    temp[0] = DP[index][i - 1][0] + V[i - 1][0];
    for(int j = 1; j < C; j++)
    {
      temp[j] = min(temp[j - 1] + H[i][j - 1], DP[index][i - 1][j] + V[i - 1][j]);
    }
    int dp = DP[index][i - 1][C - 1] + V[i - 1][C - 1];
    for(int j = C - 2; j >= 0; j--)
    {
      dp = min(dp + H[i][j], DP[index][i - 1][j] + V[i - 1][j]);
      temp[j] = min(dp, temp[j]);
    }
    bool diff = false;
    for(int j = 0; j < C; j++) if(temp[j] != DP[index][i][j]) {diff = true; break;}
    if(!diff) break;
    for(int j = 0; j < C; j++) DP[index][i][j] = temp[j];
  }
  return;
}
void init(int r, int c, int h[5000][200], int v[5000][200])
{
  R = r;
  C = 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];}
  }
  for(int i = 0; i < C; i++) I[i] = -1;
  return;
}
void changeH(int r, int c, int w)
{
  H[r][c] = w;
  for(int i = 0; i < C; i++) if(I[i] >= 0) doDP(i, r);
  return;
}
void changeV(int r, int c, int w)
{
  V[r][c] = w;
  for(int i = 0; i < C; i++) if(I[i] >= 0) doDP(i, r + 1);
  return;
}
int escape(int u, int v)
{
  if(I[u] < 0)
  {
    if(sz < 75) I[u] = sz++;
    else
    {
      int kick;
      do
      {
        kick = rng() % C;
      }while(I[kick] < 0);
      I[u] = I[kick];
      I[kick] = -1;
    }
    doDP(u);
  }
  return DP[I[u]][R - 1][v];
}
//int h[5000][200], v[5000][200];
//int main()
//{
//  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//  int r, c;
//  cin >> r >> c;
//  for(int i = 0; i < r; i++)
//  {
//    for(int j = 0; j < (c - 1); j++) cin >> h[i][j];
//  }
//  for(int i = 0; i < (r - 1); i++)
//  {
//    for(int j = 0; j < c; j++) cin >> v[i][j];
//  }
//  init(r, c, h, v);
//  int Q, t, u, v, w;
//  cin >> Q;
//  while(Q--)
//  {
//    cin >> t >> u >> v;
//    if(t == 3) cout << escape(u, v) << '\n';
//    else
//    {
//      cin >> w;
//      if(t == 1) changeH(u, v, w);
//      else changeV(u, v, w);
//    }
//  }
//  return 0;
//}

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