oj.uz

Submission #95496

# Submission time Handle Problem Language Result Execution time Memory
95496 2019-02-01T15:06:24 Z jangwonyoung Wombats (IOI13_wombats) C++14
100 / 100
 15693 ms 247108 KB 
#include "wombats.h"
#include<iostream>
using namespace std;
const int tmw=7;
const int M=5001,N=201,S=1501;
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 17 ms 18296 KB Output is correct
2 Correct 17 ms 18380 KB Output is correct
3 Correct 76 ms 20036 KB Output is correct
4 Correct 17 ms 18300 KB Output is correct
5 Correct 16 ms 18296 KB Output is correct
6 Correct 2 ms 380 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 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 756 KB Output is correct
11 Correct 67 ms 1784 KB Output is correct
12 Correct 2 ms 764 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 3932 KB Output is correct
2 Correct 257 ms 3964 KB Output is correct
3 Correct 350 ms 4216 KB Output is correct
4 Correct 324 ms 4164 KB Output is correct
5 Correct 339 ms 4216 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 1285 ms 4164 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 19 ms 23416 KB Output is correct
2 Correct 20 ms 23388 KB Output is correct
3 Correct 18 ms 23416 KB Output is correct
4 Correct 56 ms 24184 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 3992 KB Output is correct
2 Correct 251 ms 3960 KB Output is correct
3 Correct 367 ms 4180 KB Output is correct
4 Correct 327 ms 4160 KB Output is correct
5 Correct 335 ms 4216 KB Output is correct
6 Correct 21 ms 23416 KB Output is correct
7 Correct 21 ms 23416 KB Output is correct
8 Correct 22 ms 23416 KB Output is correct
9 Correct 55 ms 24184 KB Output is correct
10 Correct 17 ms 18300 KB Output is correct
11 Correct 18 ms 18296 KB Output is correct
12 Correct 72 ms 19832 KB Output is correct
13 Correct 14 ms 18296 KB Output is correct
14 Correct 14 ms 18296 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 2 ms 760 KB Output is correct
19 Correct 2 ms 764 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 760 KB Output is correct
22 Correct 2 ms 760 KB Output is correct
23 Correct 2 ms 760 KB Output is correct
24 Correct 2 ms 760 KB Output is correct
25 Correct 64 ms 1784 KB Output is correct
26 Correct 2 ms 760 KB Output is correct
27 Correct 1262 ms 4164 KB Output is correct
28 Correct 3134 ms 135408 KB Output is correct
29 Correct 3374 ms 111144 KB Output is correct
30 Correct 3487 ms 111356 KB Output is correct
31 Correct 3227 ms 136920 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 343 ms 3960 KB Output is correct
2 Correct 235 ms 4024 KB Output is correct
3 Correct 337 ms 4240 KB Output is correct
4 Correct 319 ms 4216 KB Output is correct
5 Correct 342 ms 4212 KB Output is correct
6 Correct 21 ms 23476 KB Output is correct
7 Correct 22 ms 23388 KB Output is correct
8 Correct 20 ms 23488 KB Output is correct
9 Correct 51 ms 24832 KB Output is correct
10 Correct 17 ms 18296 KB Output is correct
11 Correct 18 ms 18284 KB Output is correct
12 Correct 81 ms 20864 KB Output is correct
13 Correct 18 ms 18296 KB Output is correct
14 Correct 15 ms 18296 KB Output is correct
15 Correct 5375 ms 244596 KB Output is correct
16 Correct 15693 ms 246312 KB Output is correct
17 Correct 2 ms 292 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 1 ms 376 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 3 ms 760 KB Output is correct
22 Correct 2 ms 796 KB Output is correct
23 Correct 2 ms 788 KB Output is correct
24 Correct 2 ms 760 KB Output is correct
25 Correct 2 ms 760 KB Output is correct
26 Correct 2 ms 760 KB Output is correct
27 Correct 66 ms 3132 KB Output is correct
28 Correct 2 ms 760 KB Output is correct
29 Correct 1215 ms 4232 KB Output is correct
30 Correct 3244 ms 137872 KB Output is correct
31 Correct 13138 ms 247000 KB Output is correct
32 Correct 13105 ms 247108 KB Output is correct
33 Correct 3400 ms 113664 KB Output is correct
34 Correct 14383 ms 203336 KB Output is correct
35 Correct 3477 ms 113824 KB Output is correct
36 Correct 14592 ms 203720 KB Output is correct
37 Correct 3349 ms 139044 KB Output is correct
38 Correct 13931 ms 245512 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 15004 ms 201060 KB Output is correct