| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 805546 | Antekb | 웜뱃 (IOI13_wombats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int RMAX=5000, CMAX=200, BLOMAX=130;
int H[RMAX][CMAX], V[RMAX][CMAX], R, C, K=43, blo;
int dist[2*BLOMAX][CMAX][CMAX], pocz[BLOMAX], kon[BLOMAX], czy[BLOMAX*2];
int escape(int V1, int V2) {
int ans=dist[1][V1][V2];
int sum=0;
for(int i=V2+1; i<C; i++){
sum+=H[R-1][i-1];
ans=min(ans, dist[1][V1][i]+sum);
}
sum=0;
for(int i=V2-1; i>=0; i--){
sum+=H[R-1][i];
ans=min(ans, dist[1][V1][i]+sum);
}#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int RMAX=5000, CMAX=200, BLOMAX=130;
int H[RMAX][CMAX], V[RMAX][CMAX], R, C, K=43, blo;
int dist[2*BLOMAX][CMAX][CMAX], pocz[BLOMAX], kon[BLOMAX], czy[BLOMAX*2];
int res[CMAX][CMAX];
void get_res(){
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
res[i][j]=dist[1][i][j];
}
for(int j=1; j<C; j++){
res[i][j]=min(res[i][j], res[i][j-1]+H[R-1][j-1]);
}
for(int j=C-2; j>=0; j--){
res[i][j]=min(res[i][j+1]+H[R-1][j], res[i][j]);
}
}
}
int escape(int V1, int V2) {
/*int ans=dist[1][V1][V2];
int sum=0;
for(int i=V2+1; i<C; i++){
sum+=H[R-1][i-1];
ans=min(ans, dist[1][V1][i]+sum);
}
sum=0;
for(int i=V2-1; i>=0; i--){
sum+=H[R-1][i];
ans=min(ans, dist[1][V1][i]+sum);
}*/
//cerr<<ans<<"\n";
return res[V1][V2];
}
void update(int num){
int tab[C][C];
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
tab[i][j]=(1e9)*(i!=j);
}
}
for(int r=pocz[num]; r<=kon[num]; r++){
for(int i=0; i<C; i++){
for(int j=1; j<C; j++){
tab[i][j]=min(tab[i][j], tab[i][j-1]+H[r][j-1]);
}
for(int j=C-2; j>=0; j--){
tab[i][j]=min(tab[i][j+1]+H[r][j], tab[i][j]);
}
for(int j=0; j<C; j++){
tab[i][j]+=V[r][j];
}
}
}
//cerr<<"\n";
//cerr<<num<<"\n";
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
//cerr<<tab[i][j]<<" \n"[j==C-1];
dist[blo+num][i][j]=tab[i][j];
}
}
//cerr<<"\n";
}
void lacz(int v){
if(!czy[v])return;
int l=v+v, r=v+v+1;
if(!czy[r]){
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
dist[v][i][j]=dist[l][i][j];
}
}
}
else{
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
dist[v][i][j]=1e9;
for(int k=0; k<C; k++){
dist[v][i][j]=min(dist[v][i][j], dist[l][i][k]+dist[r][k][j]);
}
}
}
}
/*cerr<<"\n";
cerr<<v<<"a\n";
cerr<<l<<" "<<r<<"\n";
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<dist[v][i][j]<<" \n"[j==C-1];
}
}
cerr<<"\n";*/
}
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*K<R-1; i++){
blo++;
}
while(__builtin_popcount(blo)>1)blo++;
for(int i=0; i*K<R-1; i++){
pocz[i]=i*K;
kon[i]=min((i+1)*K-1, R-2);
update(i);
czy[i+blo]=1;
}
for(int i=blo-1; i>0; i--){
czy[i]=(czy[i+i]|czy[i+i+1]);
lacz(i);
}
get_res();
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
void changeH(int P, int Q, int W) {
H[P][Q]=W;
if(P!=R-1){
update(P/K);
int v=P/K+blo;
v/=2;
while(v){
lacz(v);
v/=2;
}
}
get_res();
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
update(P/K);
int v=P/K+blo;
v/=2;
while(v){
lacz(v);
v/=2;
}
get_res();
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
tab[i][j]=(1e9)*(i!=j);
}
}
for(int r=pocz[num]; r<=kon[num]; r++){
for(int i=0; i<C; i++){
for(int j=1; j<C; j++){
tab[i][j]=min(tab[i][j], tab[i][j-1]+H[r][j-1]);
}
for(int j=C-2; j>=0; j--){
tab[i][j]=min(tab[i][j+1]+H[r][j], tab[i][j]);
}
for(int j=0; j<C; j++){
tab[i][j]+=V[r][j];
}
}
}
//cerr<<"\n";
//cerr<<num<<"\n";
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
//cerr<<tab[i][j]<<" \n"[j==C-1];
dist[blo+num][i][j]=tab[i][j];
}
}
//cerr<<"\n";
}
void lacz(int v){
if(!czy[v])return;
int l=v+v, r=v+v+1;
if(!czy[r]){
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
dist[v][i][j]=dist[l][i][j];
}
}
}
else{
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
dist[v][i][j]=1e9;
for(int k=0; k<C; k++){
dist[v][i][j]=min(dist[v][i][j], dist[l][i][k]+dist[r][k][j]);
}
}
}
}
/*cerr<<"\n";
cerr<<v<<"a\n";
cerr<<l<<" "<<r<<"\n";
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<dist[v][i][j]<<" \n"[j==C-1];
}
}
cerr<<"\n";*/
}
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*K<R-1; i++){
blo++;
}
while(__builtin_popcount(blo)>1)blo++;
for(int i=0; i*K<R-1; i++){
pocz[i]=i*K;
kon[i]=min((i+1)*K-1, R-2);
update(i);
czy[i+blo]=1;
}
for(int i=blo-1; i>0; i--){
czy[i]=(czy[i+i]|czy[i+i+1]);
lacz(i);
}
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
void changeH(int P, int Q, int W) {
H[P][Q]=W;
if(P!=R-1){
update(P/K);
int v=P/K+blo;
v/=2;
while(v){
lacz(v);
v/=2;
}
}
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
update(P/K);
int v=P/K+blo;
v/=2;
while(v){
lacz(v);
v/=2;
}
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}