Submission #1263769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263769		repmann	Wombats (IOI13_wombats)	C++20	39 / 100	50 ms	20040 KiB

wombats

#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
int R, C;
int H[5000][200], V[5000][200];
int TOP[200][200], BOT[200][200], TOPMEM[200][1000][200], BOTMEM[200][1000][200], DP[2][200];
int P[2501], I[5000];
inline void TopDP(int u, int row)
{
  int start = -1;
  if(row >= 0) for(int i = row - 3; i >= 0; i--) if(I[i] >= 0) {start = i; break;}
//  cout << row << ' ' << start << '\n';
  if(start < 0)
  {
    DP[0][u] = 0;
    for(int i = u - 1; i >= 0; i--) DP[0][i] = DP[0][i + 1] + H[0][i];
    for(int i = u + 1; i < C; i++) DP[0][i] = DP[0][i - 1] + H[0][i - 1];
    if(I[0] >= 0) __builtin_memcpy(TOPMEM[u][I[0]], DP[0], C << 2);
    start = 0;
  }
  else __builtin_memcpy(DP[0], TOPMEM[u][I[start]], C << 2);
  for(int i = start + 1; i <= (R >> 1); i++)
  {
    DP[1][0] = DP[0][0] + V[i - 1][0];
    for(int j = 1; j < C; j++) DP[1][j] = min(DP[1][j - 1] + H[i][j - 1], DP[0][j] + V[i - 1][j]);
    int dp = DP[0][C - 1] + V[i - 1][C - 1];
    DP[1][C - 1] = min(dp, DP[1][C - 1]);
    for(int j = C - 2; j >= 0; j--)
    {
      dp = min(dp + H[i][j], DP[0][j] + V[i - 1][j]);
      DP[1][j] = min(dp, DP[1][j]);
    }
    if(I[i] >= 0)
    {
      bool flag = ((i - 1) <= row) || (row < 0);
      for(int j = 0; (j < C) && !flag; j++) flag = TOPMEM[u][I[i]][j] != DP[1][j];
      if(!flag) return;
      else __builtin_memcpy(TOPMEM[u][I[i]], DP[1], C << 2);
    }
    __builtin_memcpy(DP[0], DP[1], C << 2);
  }
  for(int i = 0; i < C; i++) TOP[u][i] = DP[0][i];
  return;
}
inline void BotDP(int v, int row)
{
  int start = -1;
  if(row >= 0) for(int i = row + 3; i < R; i++) if(I[i] >= 0) {start = i; break;}
//  cout << row << ' ' << start << '\n';
  if(start < 0)
  {
    DP[0][v] = 0;
    for(int i = v - 1; i >= 0; i--) DP[0][i] = DP[0][i + 1] + H[R - 1][i];
    for(int i = v + 1; i < C; i++) DP[0][i] = DP[0][i - 1] + H[R - 1][i - 1];
    if(I[R - 1] >= 0) __builtin_memcpy(BOTMEM[v][I[R - 1]], DP[0], C << 2);
    start = R - 1;
  }
  else __builtin_memcpy(DP[0], BOTMEM[v][I[start]], C << 2);
  for(int i = start - 1; i > (R >> 1); i--)
  {
    DP[1][0] = DP[0][0] + V[i][0];
    for(int j = 1; j < C; j++) DP[1][j] = min(DP[1][j - 1] + H[i][j - 1], DP[0][j] + V[i][j]);
    int dp = DP[0][C - 1] + V[i][C - 1];
    DP[1][C - 1] = min(dp, DP[1][C - 1]);
    for(int j = C - 2; j >= 0; j--)
    {
      dp = min(dp + H[i][j], DP[0][j] + V[i][j]);
      DP[1][j] = min(dp, DP[1][j]);
    }
    if(I[i] >= 0)
    {
      bool flag = ((i + 1) >= row) || (row < 0);
      for(int j = 0; (j < C) && !flag; j++) flag = BOTMEM[v][I[i]][j] != DP[1][j];
      if(!flag) return;
      else __builtin_memcpy(BOTMEM[v][I[i]], DP[1], C << 2);
    }
    __builtin_memcpy(DP[0], DP[1], C << 2);
  }
  for(int i = 0; i < C; i++) BOT[v][i] = DP[0][i];
  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 < R; i++) I[i] = -1;
  for(int i = 0; i <= (R >> 1); i++) P[i] = i;
  random_shuffle(P, P + (R >> 1) + 1);
//  for(int i = 0; i <= min(999, R >> 1); i++) cout << P[i] << " \n"[i == min(999, R >> 1)];
  for(int i = 0; i <= min(999, R >> 1); i++) I[P[i]] = i;
  for(int i = (R >> 1) + 1; i < R; i++) P[i - (R >> 1) - 1] = i;
  random_shuffle(P, P + R - (R >> 1));
//  for(int i = 0; i <= min(999, R - (R >> 1) - 2); i++) cout << P[i] << " \n"[i == min(999, R - (R >> 1) - 2)];
  for(int i = 0; i <= min(999, R - (R >> 1) - 2); i++) I[P[i]] = i;
//  cout << "I:\n";
//  for(int i = 0; i < R; i++) cout << I[i] << " \n"[i == (R - 1)];
//  cout << "PREV:\n";
//  for(int i = 0; i < R; i++) cout << PREV[i] << " \n"[i == (R - 1)];
  for(int i = 0; i < C; i++) TopDP(i, -1);
  for(int i = 0; i < C; i++) BotDP(i, -1);
  return;
}
void changeH(int r, int c, int w)
{
  H[r][c] = w;
  if(r <= (R >> 1)) for(int i = 0; i < C; i++) TopDP(i, r);
  else for(int i = 0; i < C; i++) BotDP(i, r);
  return;
}
void changeV(int r, int c, int w)
{
  V[r][c] = w;
  if(r < (R >> 1)) for(int i = 0; i < C; i++) TopDP(i, r);
  else if(r > (R >> 1)) for(int i = 0; i < C; i++) BotDP(i, r);
  return;
}
int escape(int u, int v)
{
  int ret = INT_MAX;
  for(int i = 0; i < C; i++) ret = min(TOP[u][i] + V[R >> 1][i] + BOT[v][i], ret);
  return ret;
}
//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: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24