oj.uz

Submission #95488

# Submission time Handle Problem Language Result Execution time Memory
95488 2019-02-01T14:37:17 Z jangwonyoung Wombats (IOI13_wombats) C++14
100 / 100
 17581 ms 191904 KB 
#include "wombats.h"
#include<iostream>
using namespace std;
const int tmw=14;
const int M=5001,N=201,S=1501;
int m,n;
int dp[S][N][N];
int dp2[32][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;
	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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16548 KB Output is correct
2 Correct 16 ms 16632 KB Output is correct
3 Correct 71 ms 18168 KB Output is correct
4 Correct 14 ms 16604 KB Output is correct
5 Correct 14 ms 16632 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 376 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 1016 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 4 ms 888 KB Output is correct
11 Correct 67 ms 1828 KB Output is correct
12 Correct 2 ms 888 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 4004 KB Output is correct
2 Correct 363 ms 3980 KB Output is correct
3 Correct 485 ms 3960 KB Output is correct
4 Correct 469 ms 3960 KB Output is correct
5 Correct 524 ms 3932 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 1925 ms 4008 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 23 ms 21368 KB Output is correct
2 Correct 17 ms 21340 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 49 ms 22748 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 4124 KB Output is correct
2 Correct 367 ms 4088 KB Output is correct
3 Correct 502 ms 3960 KB Output is correct
4 Correct 472 ms 4216 KB Output is correct
5 Correct 509 ms 3960 KB Output is correct
6 Correct 19 ms 21368 KB Output is correct
7 Correct 17 ms 21368 KB Output is correct
8 Correct 18 ms 21496 KB Output is correct
9 Correct 50 ms 22772 KB Output is correct
10 Correct 14 ms 16632 KB Output is correct
11 Correct 13 ms 16632 KB Output is correct
12 Correct 74 ms 19448 KB Output is correct
13 Correct 16 ms 16760 KB Output is correct
14 Correct 16 ms 16632 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 892 KB Output is correct
19 Correct 3 ms 888 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 752 KB Output is correct
24 Correct 3 ms 760 KB Output is correct
25 Correct 67 ms 3204 KB Output is correct
26 Correct 3 ms 888 KB Output is correct
27 Correct 1915 ms 4092 KB Output is correct
28 Correct 3553 ms 106252 KB Output is correct
29 Correct 3586 ms 102864 KB Output is correct
30 Correct 3626 ms 102844 KB Output is correct
31 Correct 3618 ms 107900 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 494 ms 4000 KB Output is correct
2 Correct 381 ms 3980 KB Output is correct
3 Correct 504 ms 4024 KB Output is correct
4 Correct 476 ms 4088 KB Output is correct
5 Correct 508 ms 4060 KB Output is correct
6 Correct 21 ms 21368 KB Output is correct
7 Correct 17 ms 21368 KB Output is correct
8 Correct 19 ms 21496 KB Output is correct
9 Correct 54 ms 22776 KB Output is correct
10 Correct 14 ms 16632 KB Output is correct
11 Correct 16 ms 16632 KB Output is correct
12 Correct 80 ms 19448 KB Output is correct
13 Correct 14 ms 16636 KB Output is correct
14 Correct 14 ms 16632 KB Output is correct
15 Correct 5340 ms 190768 KB Output is correct
16 Correct 17581 ms 191904 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 916 KB Output is correct
21 Correct 2 ms 888 KB Output is correct
22 Correct 3 ms 884 KB Output is correct
23 Correct 3 ms 888 KB Output is correct
24 Correct 3 ms 760 KB Output is correct
25 Correct 3 ms 760 KB Output is correct
26 Correct 3 ms 760 KB Output is correct
27 Correct 67 ms 3316 KB Output is correct
28 Correct 3 ms 880 KB Output is correct
29 Correct 1899 ms 4088 KB Output is correct
30 Correct 3436 ms 106276 KB Output is correct
31 Correct 14692 ms 189516 KB Output is correct
32 Correct 14523 ms 189492 KB Output is correct
33 Correct 3644 ms 102708 KB Output is correct
34 Correct 14873 ms 185584 KB Output is correct
35 Correct 3651 ms 102816 KB Output is correct
36 Correct 14982 ms 185328 KB Output is correct
37 Correct 3782 ms 107840 KB Output is correct
38 Correct 15131 ms 189864 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 15470 ms 185576 KB Output is correct