Submission #1149501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149501		epicci23	Wombats (IOI13_wombats)	C++20	0 / 100	19799 ms	50536 KiB

wombats

#include "bits/stdc++.h"
#include "wombats.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int C = 205;
const int R = 5005;
const int BL = 73;
const int INF = 3000000005;

int dp[4*BL][C][C],calc[BL][C][C];
int H[R][C],V[R][C],Lf[BL],Rg[BL],n,m;

inline void upd_block(int ind){
  int Old[C][C],New[C][C];

  for(int i=0;i<C;i++) for(int j=0;j<C;j++) Old[i][j] = New[i][j] = INF;

  for(int i=0;i<m;i++){
  	int cur = 0;
  	Old[i][i] = V[Lf[ind]][i];
  	for(int j=i-1;j>=0;j--){
  	  cur += H[Lf[ind]][j];
      Old[i][j] = cur + V[Lf[ind]][j];
  	}
  	cur = 0;
  	for(int j=i+1;j<m;j++){
  	  cur += H[Lf[ind]][j-1];
      Old[i][j] = cur + V[Lf[ind]][j];
  	}
  }

  for(int z=Lf[ind]+1;z<=Rg[ind];z++){
    for(int i=0;i<C;i++) for(int j=0;j<C;j++) New[i][j] = INF;
    
    int sum[C],cur_sum = 0;
    for(int i=0;i<m;i++){
      sum[i] = cur_sum;
      cur_sum += H[z][i];
    }

    for(int i=0;i<m;i++){
      int pre_dp[C],suf_dp[C];
      for(int j=0;j<C;j++) pre_dp[j]=suf_dp[j]=INF;
      
      int hm = INF;
      for(int j=0;j<m;j++){
        hm = min(hm, Old[i][j] - sum[j]);
        pre_dp[j] = hm;
      }
     
      hm = INF;
      for(int j=m-1;j>=0;j--){
        hm = min(hm, Old[i][j] + sum[j]);
        suf_dp[j] = hm;
      }

      for(int j=0;j<m;j++){
        New[i][j] = min(New[i][j], V[z][j] + pre_dp[j] + sum[j]);
        New[i][j] = min(New[i][j], V[z][j] + suf_dp[j] - sum[j]);
      }
    }

    for(int i=0;i<C;i++) for(int j=0;j<C;j++) Old[i][j] = New[i][j];  
  }

  for(int i=0;i<C;i++) for(int j=0;j<C;j++) calc[ind][i][j] = Old[i][j];
}

inline void merge(int rt){
  for(int i=0;i<C;i++) for(int j=0;j<C;j++) dp[rt][i][j] = INF;

  for(int i=0;i<C;i++) 
  	for(int j=0;j<C;j++) 
  		for(int k=0;k<C;k++) 
  		  dp[rt][i][k] = min(dp[rt][i][k], dp[rt*2][i][j] + dp[rt*2+1][j][k]);
}

void build(int rt,int l,int r){
  if(l==r){
  	for(int i=0;i<C;i++) for(int j=0;j<C;j++) dp[rt][i][j] = calc[l][i][j];
    return;
  }
  int mid=(l+r)/2;
  build(rt*2,l,mid),build(rt*2+1,mid+1,r);
  merge(rt);	
}

void upd(int rt,int l,int r,int ind){
  if(l > ind || r < ind) return;
  if(l == r){
  	for(int i=0;i<C;i++) for(int j=0;j<C;j++) dp[rt][i][j] = calc[ind][i][j];
    return;
  }
  int mid = (l+r)/2;
  upd(rt*2,l,mid,ind),upd(rt*2+1,mid+1,r,ind);
  merge(rt);
}

void init(int _r, int _c, int _H[5000][200], int _V[5000][200]){
  n = _r, m = _c;

  for(int i=0;i<n;i++){
    int u = i / BL;
    Rg[u] = i;
    if(i % BL == 0) Lf[u] = i;
  }

  for(int i=0;i<n;i++) for(int j=0;j+1<m;j++) H[i][j] = _H[i][j];
  for(int i=0;i+1<n;i++) for(int j=0;j<m;j++) V[i][j] = _V[i][j];
  for(int i=0;i<m;i++) V[n-1][i] = 0;
  // son blok seyini hallet

  for(int i=0;i<=(n-1)/BL;i++) upd_block(i);
  build(1,0,(n-1)/BL);
}

void changeH(int P, int Q, int W){
   H[P][Q] = W;
   upd_block(P/BL);
   upd(1,0,(n-1)/BL,P/BL); 
}

void changeV(int P, int Q, int W){
   V[P][Q] = W;
   upd_block(P/BL);
   upd(1,0,(n-1)/BL,P/BL);
}

int escape(int V1, int V2){
   return dp[1][V1][V2];
}

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