Submission #1149668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149668		epicci23	Wombats (IOI13_wombats)	C++20	100 / 100	3216 ms	190028 KiB

wombats

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

const ll C = 205;
const ll R = 5095;
const ll BL = 20;
const ll INF = 3000000005;

ll dp[4*(R/BL)][C][C],H[R][C],V[R][C],Lf[R],Rg[R],Index[R],n,m;
ll Old[C][C],New[C][C],Opt[C][C];

inline void upd_block(ll ind){
  for(ll i=0;i<C;i++) for(ll j=0;j<C;j++) Old[i][j] = New[i][j] = INF;

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

  for(ll z=Lf[ind]+1;z<=Rg[ind];z++){
    for(ll i=0;i<C;i++) for(ll j=0;j<C;j++) New[i][j] = INF;

    for(ll i=0;i<m;i++){
      ll hm = INF,cur_sum = 0;
      for(ll j=0;j<m;j++){
        hm = min(hm, Old[i][j] - cur_sum);
        New[i][j] = min(New[i][j], V[z][j] + hm + cur_sum);
        cur_sum += H[z][j];
      }
      hm = INF,cur_sum = 0;
      for(ll j=m-1;j>=0;j--){
        cur_sum += H[z][j];
        hm = min(hm, Old[i][j] - cur_sum); 
        New[i][j] = min(New[i][j], V[z][j] + hm + cur_sum);
      }
    }

    for(ll i=0;i<C;i++) for(ll j=0;j<C;j++) Old[i][j] = New[i][j];  
  }
  for(ll i=0;i<C;i++) for(ll j=0;j<C;j++) dp[Index[ind]][i][j] = Old[i][j];
}

inline void merge(ll rt){
  for(ll dif = m - 1; dif >= -(m-1); --dif){
    for(ll s = 0; s < m; ++s){
      ll e = s - dif;
      if(e >= 0 && e < m){
        ll lb = e == 0 ? 0 : Opt[s][e - 1];
        ll rb = s == m - 1 ? m - 1 : Opt[s + 1][e];
        dp[rt][s][e] = INF;
        Opt[s][e] = lb;
        for(ll j = lb; j <= rb; ++j){
          ll val = dp[rt<<1][s][j] + dp[rt<<1|1][j][e];
          if(dp[rt][s][e] > val){
            Opt[s][e] = j;
            dp[rt][s][e] = val;
          }
        }
      }
    }
  }
}

void Find(ll rt,ll l,ll r){
  if(l==r){
    Index[l] = rt;
    return;
  }
  ll mid=(l+r)/2;
  Find(rt*2,l,mid),Find(rt*2+1,mid+1,r);
}

void build(ll rt,ll l,ll r){
  if(l==r) return;
  ll mid=(l+r)/2;
  build(rt*2,l,mid),build(rt*2+1,mid+1,r);
  merge(rt);	
}

inline void upd(ll rt){
  while(rt > 1){
   merge(rt / 2);
   rt/=2;
  }
}

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

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

  for(ll i=0;i<n;i++) for(ll j=0;j+1<m;j++) H[i][j] = _H[i][j];
  for(ll i=0;i+1<n;i++) for(ll j=0;j<m;j++) V[i][j] = _V[i][j];
  Find(1,0,(n-1)/BL);

  for(ll 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(Index[P/BL]); 
}

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

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

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