| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1303511 | activedeltorre | 웜뱃 (IOI13_wombats) | C++20 | 0 ms | 0 KiB |
//#include "wombats.h"
#include <iostream>
using namespace std;
int math[5005][102];
int matv[5005][102];
int aint[18005][102][102];
int spar[205];
int bucket=0,c,r;
int inf=50000000;
void build(int node,int st,int dr)
{
if(dr-st<=bucket)
{
for(int i=1; i<c; i++)
{
spar[i]=spar[i-1]+math[st][i-1];
}
for(int i=0; i<c; i++)
{
for(int j=0; j<c; j++)
{
aint[node][i][j]=spar[max(i,j)]-spar[min(i,j)];
}
}
return;
}
int mij=(st+dr)/2;
build(node*2,st,mij);
build(node*2+1,mij+1,dr);
for(int i=0; i<c; i++)
{
for(int j=0; j<c; j++)
{
aint[node][i][j]=inf;
for(int z=0; z<c; z++)
{
aint[node][i][j]=min(aint[node][i][j],aint[node*2][i][z]+aint[node*2+1][z][j]+matv[mij][z]);
}
}
}
}
void recalc(int node,int st,int dr,int poz)
{
if(poz==st && poz==dr)
{
for(int i=1; i<c; i++)
{
spar[i]=spar[i-1]+math[st][i-1];
}
for(int i=0; i<c; i++)
{
for(int j=0; j<c; j++)
{
aint[node][i][j]=spar[max(i,j)]-spar[min(i,j)];
}
}
return;
}
if(poz>dr || poz<st)
{
return;
}
int mij=(st+dr)/2;
recalc(node*2,st,mij,poz);
recalc(node*2+1,mij+1,dr,poz);
for(int i=0; i<c; i++)
{
for(int j=0; j<c; j++)
{
aint[node][i][j]=inf;
for(int z=0; z<c; z++)
{
aint[node][i][j]=min(aint[node][i][j],aint[node*2][i][z]+aint[node*2+1][z][j]+matv[mij][z]);
}
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
c=C;
r=R;
for(int i=0; i<R; i++)
{
for(int j=0; j<C-1; j++)
{
math[i][j]=H[i][j];
}
}
for(int i=0; i<R-1; i++)
{
for(int j=0; j<C; j++)
{
matv[i][j]=V[i][j];
}
}
build(1,0,r-1);
}
void changeH(int P, int Q, int W)
{
math[P][Q]=W;
recalc(1,0,r-1,P);
}
void changeV(int P, int Q, int W)
{
matv[P][Q]=W;
recalc(1,0,r-1,P);
}
int escape(int V1, int V2)
{
int minim=inf;
int mij=(r-1)/2;
for(int i=0;i<c;i++)
{
minim=min(minim,aint[2][V1][i]+aint[3][i][V2]+matv[mij][i]);
}
return minim;
}