oj.uz

답안 #95485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95485 2019-02-01T14:27:25 Z jangwonyoung 웜뱃 (IOI13_wombats) C++14
28 / 100
 1281 ms 47224 KB 
#include "wombats.h"
#include<iostream>
using namespace std;
const int tmw=7;
int m,n;
int dp[1501][201][201];
int dp2[16][201][201];
int lc[1501],rc[1501];
int h[5001][201],v[5001][201];
void cal(int id,int st,int l,int r,int optl,int optr){
	if(l>r) return;
	int opt=0,mid=(l+r)/2;
	dp[id][st][mid]=1e9;
	for(int i=optl; i<=optr ;i++)
		if(dp[id][st][mid]>dp[lc[id]][st][i]+dp[rc[id]][i][mid])
			dp[id][st][mid]=dp[lc[id]][st][i]+dp[rc[id]][i][mid],opt=i;
	cal(id,st,l,mid-1,optl,opt);
	cal(id,st,mid+1,r,opt,optr);
}
void cal2(int id,int st,int l,int r,int optl,int optr){
	if(l>r) return;
	int opt=0,mid=(l+r)/2;
	dp2[id][st][mid]=1e9;
	for(int i=optl; i<=optr ;i++)
		if(dp2[id][st][mid]>dp2[id*2][st][i]+dp2[id*2+1][i][mid])
			dp2[id][st][mid]=dp2[id*2][st][i]+dp2[id*2+1][i][mid],opt=i;
	cal2(id,st,l,mid-1,optl,opt);
	cal2(id,st,mid+1,r,opt,optr);
}
void upd2(int id,int l,int r){
	if(l==r){
		for(int i=1; i<=n ;i++){
			dp2[id][i][i]=v[l][i];
			for(int j=i+1; j<=n ;j++)
				dp2[id][i][j]=dp2[id][i][j-1]-v[l][j-1]+v[l][j]+h[l][j-1];
			for(int j=i-1; j>=1 ;j--)
				dp2[id][i][j]=dp2[id][i][j+1]-v[l][j+1]+v[l][j]+h[l][j];
			for(int j=1+1; j<=n ;j++) dp2[id][i][j]=min(dp2[id][i][j],dp2[id][i][j-1]+h[l+1][j-1]);
			for(int j=n-1; j>=1 ;j--) dp2[id][i][j]=min(dp2[id][i][j],dp2[id][i][j+1]+h[l+1][j]);
			//cout << id << ' ' << l << ' ' << i << ": ";
			//for(int j=1; j<=n ;j++) cout << dp2[id][i][j] << ' ';
			//cout << endl;
		}
		return;
	}
	int mid=(l+r)/2;
	upd2(id*2,l,mid);upd2(id*2+1,mid+1,r);
	for(int i=1; i<=n ;i++) cal2(id,i,1,n,1,n);
}
void upd(int id,int l,int r,int x,int y){
	if((l>x || x>r) && (l>y || y>r)) return;
	if(r-l<tmw){
		upd2(1,l,r);
		for(int i=1; i<=n ;i++) for(int j=1; j<=n ;j++) dp[id][i][j]=dp2[1][i][j];
		return;
	}
	int mid=(l+r)/2;
	upd(lc[id],l,mid,x,y);
	upd(rc[id],mid+1,r,x,y);
	for(int i=1; i<=n ;i++) cal(id,i,1,n,1,n);
}
int ptr=1;
void build(int id,int l,int r){
	if(r-l<tmw){
		upd2(1,l,r);
		for(int i=1; i<=n ;i++) for(int j=1; j<=n ;j++) dp[id][i][j]=dp2[1][i][j];
		return;
	}
	lc[id]=++ptr;rc[id]=++ptr;
	int mid=(l+r)/2;
	build(lc[id],l,mid);build(rc[id],mid+1,r);
	for(int i=1; i<=n ;i++) cal(id,i,1,n,1,n);
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
	m=R;n=C;
	for(int i=0; i<m ;i++)
		for(int j=0; j<n ;j++)
			h[i+1][j+1]=H[i][j],v[i+1][j+1]=V[i][j];
	build(1,1,m-1);
}
void changeH(int P, int Q, int W){
	int p=P+1,q=Q+1,w=W;
    h[p][q]=w;
    upd(1,1,m-1,p-1,p);
}
void changeV(int P, int Q, int W){
	int p=P+1,q=Q+1,w=W;
    v[p][q]=w;
    upd(1,1,m-1,p,p);
}
int escape(int V1, int V2){
    int p=V1+1,q=V2+1;
    return dp[1][p][q];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 53 ms 36984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 3 ms 764 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 66 ms 1784 KB Output is correct
12 Correct 3 ms 760 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 4364 KB Output is correct
2 Correct 235 ms 4216 KB Output is correct
3 Correct 334 ms 4328 KB Output is correct
4 Correct 307 ms 4328 KB Output is correct
5 Correct 313 ms 4344 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 1281 ms 4332 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 63 ms 47224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 327 ms 4448 KB Output is correct
2 Correct 228 ms 4216 KB Output is correct
3 Correct 342 ms 4444 KB Output is correct
4 Correct 311 ms 4216 KB Output is correct
5 Correct 335 ms 4328 KB Output is correct
6 Runtime error 77 ms 47224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 4344 KB Output is correct
2 Correct 240 ms 4304 KB Output is correct
3 Correct 341 ms 4444 KB Output is correct
4 Correct 292 ms 4328 KB Output is correct
5 Correct 310 ms 4216 KB Output is correct
6 Runtime error 77 ms 47224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -