oj.uz

Submission #95495

# Submission time Handle Problem Language Result Execution time Memory
95495 2019-02-01T15:04:48 Z jangwonyoung Wombats (IOI13_wombats) C++14
100 / 100
 16409 ms 219832 KB 
#include "wombats.h"
#include<iostream>
using namespace std;
const int tmw=8;
const int M=5001,N=201,S=1301;
int m,n;
int dp[S][N][N];
int dp2[16][N][N];
int lc[S],rc[S];
int h[M][N],v[M][N];
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;
	mid+=(tmw-mid%tmw)%tmw;
	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;
	mid+=(tmw-mid%tmw)%tmw;
	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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17528 KB Output is correct
2 Correct 17 ms 17528 KB Output is correct
3 Correct 80 ms 19456 KB Output is correct
4 Correct 17 ms 17528 KB Output is correct
5 Correct 14 ms 17528 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 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 3 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 69 ms 2168 KB Output is correct
12 Correct 4 ms 888 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 4020 KB Output is correct
2 Correct 278 ms 3960 KB Output is correct
3 Correct 389 ms 3960 KB Output is correct
4 Correct 355 ms 4080 KB Output is correct
5 Correct 382 ms 3960 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 1412 ms 4216 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22520 KB Output is correct
2 Correct 18 ms 22520 KB Output is correct
3 Correct 18 ms 22520 KB Output is correct
4 Correct 52 ms 23716 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 4116 KB Output is correct
2 Correct 276 ms 3960 KB Output is correct
3 Correct 377 ms 4092 KB Output is correct
4 Correct 363 ms 4088 KB Output is correct
5 Correct 365 ms 4088 KB Output is correct
6 Correct 21 ms 22520 KB Output is correct
7 Correct 21 ms 22520 KB Output is correct
8 Correct 22 ms 22520 KB Output is correct
9 Correct 54 ms 23800 KB Output is correct
10 Correct 17 ms 17656 KB Output is correct
11 Correct 17 ms 17656 KB Output is correct
12 Correct 78 ms 19708 KB Output is correct
13 Correct 17 ms 17656 KB Output is correct
14 Correct 17 ms 17656 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 888 KB Output is correct
19 Correct 3 ms 760 KB Output is correct
20 Correct 3 ms 888 KB Output is correct
21 Correct 3 ms 888 KB Output is correct
22 Correct 3 ms 760 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 2 ms 760 KB Output is correct
25 Correct 66 ms 2296 KB Output is correct
26 Correct 3 ms 888 KB Output is correct
27 Correct 1400 ms 4092 KB Output is correct
28 Correct 3300 ms 121088 KB Output is correct
29 Correct 3525 ms 99836 KB Output is correct
30 Correct 3596 ms 99768 KB Output is correct
31 Correct 3410 ms 122212 KB Output is correct
32 Correct 2 ms 376 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 3960 KB Output is correct
2 Correct 267 ms 3980 KB Output is correct
3 Correct 361 ms 4088 KB Output is correct
4 Correct 362 ms 4088 KB Output is correct
5 Correct 372 ms 4216 KB Output is correct
6 Correct 19 ms 22524 KB Output is correct
7 Correct 18 ms 22520 KB Output is correct
8 Correct 22 ms 22524 KB Output is correct
9 Correct 50 ms 23804 KB Output is correct
10 Correct 14 ms 17528 KB Output is correct
11 Correct 14 ms 17528 KB Output is correct
12 Correct 73 ms 19632 KB Output is correct
13 Correct 15 ms 17528 KB Output is correct
14 Correct 14 ms 17656 KB Output is correct
15 Correct 5304 ms 216168 KB Output is correct
16 Correct 16409 ms 218076 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 888 KB Output is correct
21 Correct 2 ms 888 KB Output is correct
22 Correct 2 ms 760 KB Output is correct
23 Correct 2 ms 888 KB Output is correct
24 Correct 0 ms 760 KB Output is correct
25 Correct 2 ms 888 KB Output is correct
26 Correct 2 ms 764 KB Output is correct
27 Correct 66 ms 2296 KB Output is correct
28 Correct 3 ms 760 KB Output is correct
29 Correct 1437 ms 4088 KB Output is correct
30 Correct 3347 ms 121212 KB Output is correct
31 Correct 13626 ms 217180 KB Output is correct
32 Correct 13466 ms 217160 KB Output is correct
33 Correct 3495 ms 99804 KB Output is correct
34 Correct 14889 ms 178656 KB Output is correct
35 Correct 3584 ms 99768 KB Output is correct
36 Correct 14893 ms 178924 KB Output is correct
37 Correct 3460 ms 122724 KB Output is correct
38 Correct 13881 ms 219832 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 15564 ms 180572 KB Output is correct