oj.uz

Submission #126151

# Submission time Handle Problem Language Result Execution time Memory
126151 2019-07-07T06:10:47 Z nxteru Wombats (IOI13_wombats) C++14
100 / 100
 8176 ms 186872 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
#define B 10
struct node{
	int n,d[200][200];
	void ini(int x){
		n=x;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(i==j)d[i][j]=0;
				else d[i][j]=INF;
			}
		}
	}
	node plus(node &q){
		node res;
		res.ini(n);
		int a[205][205],s;
		for(int i=n-1;i>-n;i--){
			for(int j=max(-i,0);i+j<n&&j<n;j++){
				s=INF;
				int x,y;
				if(j-1>=0)x=a[i+j][j-1];
				else x=0;
				if(i+j+1<n)y=a[i+j+1][j];
				else y=n-1;
				for(int k=x;k<=y;k++){
					if(d[i+j][k]+q.d[k][j]<s){
						x=k;
						s=d[i+j][k]+q.d[k][j];
					}
				}
				a[i+j][j]=x;
				res.d[i+j][j]=min(s,INF);
			}
		}
		return res;
	}
};
struct SEG{
	int n;
	node seg[1<<10];
	void ini(int x){
		n=x;
		for(int i=0;i<1<<10;i++)seg[i].ini(n);
	}
	void up(int a,node &q){
		a+=(1<<9)-1;
		seg[a]=q;
		while(a>0){
			a=(a-1)/2;
			seg[a]=seg[a*2+1].plus(seg[a*2+2]);
		}
	}
};
int h[5005][205],w[5005][205],n,m,p[205][205];
SEG s;
void change(int x){
	x=x/B;
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(i==j)p[i][j]=0;
			else p[i][j]=INF;
		}
	}
	for(int i=0;i<B&&x*B+i<n;i++){
		for(int j=0;j<m;j++){
			int *q=p[j];
			for(int k=1;k<m;k++)q[k]=min(q[k],q[k-1]+h[x*B+i][k-1]);
			for(int k=m-2;k>=0;k--)q[k]=min(q[k],q[k+1]+h[x*B+i][k]);
			for(int k=0;k<m;k++)q[k]+=w[x*B+i][k];
		}
	}
	node res;
	res.n=m;
	for(int i=0;i<m;i++)for(int j=0;j<m;j++)res.d[i][j]=p[i][j];
	s.up(x,res);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
   n=R,m=C;
   s.ini(m);
   for(int i=0;i<n;i++)for(int j=0;j<m-1;j++)h[i][j]=H[i][j];
   for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)w[i][j]=V[i][j];
   for(int i=0;i<n;i+=B)change(i);
}
void changeH(int a, int b, int x) {
    h[a][b]=x;
    change(a);
}
 
void changeV(int a, int b, int x) {
    w[a][b]=x;
    change(a);
}
 
int escape(int a, int b) {
    return s.seg[0].d[a][b];
}

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 269 ms 165112 KB Output is correct
2 Correct 272 ms 165268 KB Output is correct
3 Correct 341 ms 167220 KB Output is correct
4 Correct 290 ms 165212 KB Output is correct
5 Correct 270 ms 165192 KB Output is correct
6 Correct 7 ms 6264 KB Output is correct
7 Correct 7 ms 6264 KB Output is correct
8 Correct 7 ms 6264 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6392 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 7 ms 6264 KB Output is correct
4 Correct 23 ms 21752 KB Output is correct
5 Correct 24 ms 21624 KB Output is correct
6 Correct 19 ms 21624 KB Output is correct
7 Correct 19 ms 21756 KB Output is correct
8 Correct 18 ms 20856 KB Output is correct
9 Correct 19 ms 21624 KB Output is correct
10 Correct 18 ms 20984 KB Output is correct
11 Correct 97 ms 23288 KB Output is correct
12 Correct 19 ms 21752 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 87060 KB Output is correct
2 Correct 282 ms 86348 KB Output is correct
3 Correct 303 ms 87112 KB Output is correct
4 Correct 297 ms 87036 KB Output is correct
5 Correct 292 ms 86264 KB Output is correct
6 Correct 7 ms 6392 KB Output is correct
7 Correct 8 ms 6264 KB Output is correct
8 Correct 8 ms 6264 KB Output is correct
9 Correct 1050 ms 87032 KB Output is correct
10 Correct 9 ms 8696 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 173136 KB Output is correct
2 Correct 276 ms 173176 KB Output is correct
3 Correct 292 ms 173080 KB Output is correct
4 Correct 316 ms 174072 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 87192 KB Output is correct
2 Correct 279 ms 86264 KB Output is correct
3 Correct 302 ms 87032 KB Output is correct
4 Correct 295 ms 87288 KB Output is correct
5 Correct 295 ms 86392 KB Output is correct
6 Correct 275 ms 173176 KB Output is correct
7 Correct 275 ms 173176 KB Output is correct
8 Correct 297 ms 173048 KB Output is correct
9 Correct 320 ms 174248 KB Output is correct
10 Correct 305 ms 165240 KB Output is correct
11 Correct 271 ms 165112 KB Output is correct
12 Correct 361 ms 167136 KB Output is correct
13 Correct 286 ms 165156 KB Output is correct
14 Correct 268 ms 165240 KB Output is correct
15 Correct 7 ms 6264 KB Output is correct
16 Correct 7 ms 6264 KB Output is correct
17 Correct 6 ms 6264 KB Output is correct
18 Correct 19 ms 21724 KB Output is correct
19 Correct 19 ms 21752 KB Output is correct
20 Correct 23 ms 21752 KB Output is correct
21 Correct 21 ms 21752 KB Output is correct
22 Correct 19 ms 20984 KB Output is correct
23 Correct 19 ms 21624 KB Output is correct
24 Correct 18 ms 20856 KB Output is correct
25 Correct 95 ms 23160 KB Output is correct
26 Correct 19 ms 21624 KB Output is correct
27 Correct 1031 ms 87160 KB Output is correct
28 Correct 2200 ms 176200 KB Output is correct
29 Correct 2095 ms 160192 KB Output is correct
30 Correct 2151 ms 160120 KB Output is correct
31 Correct 2239 ms 177344 KB Output is correct
32 Correct 9 ms 8696 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 87160 KB Output is correct
2 Correct 277 ms 86240 KB Output is correct
3 Correct 314 ms 87036 KB Output is correct
4 Correct 298 ms 87108 KB Output is correct
5 Correct 294 ms 86392 KB Output is correct
6 Correct 302 ms 173252 KB Output is correct
7 Correct 277 ms 173108 KB Output is correct
8 Correct 354 ms 173224 KB Output is correct
9 Correct 352 ms 173996 KB Output is correct
10 Correct 286 ms 165172 KB Output is correct
11 Correct 275 ms 165112 KB Output is correct
12 Correct 342 ms 167124 KB Output is correct
13 Correct 334 ms 165244 KB Output is correct
14 Correct 272 ms 165200 KB Output is correct
15 Correct 4122 ms 177872 KB Output is correct
16 Correct 8176 ms 186872 KB Output is correct
17 Correct 6 ms 6268 KB Output is correct
18 Correct 7 ms 6264 KB Output is correct
19 Correct 7 ms 6264 KB Output is correct
20 Correct 19 ms 21752 KB Output is correct
21 Correct 19 ms 21752 KB Output is correct
22 Correct 19 ms 21752 KB Output is correct
23 Correct 19 ms 21752 KB Output is correct
24 Correct 18 ms 20856 KB Output is correct
25 Correct 19 ms 21624 KB Output is correct
26 Correct 19 ms 20984 KB Output is correct
27 Correct 95 ms 24140 KB Output is correct
28 Correct 23 ms 21724 KB Output is correct
29 Correct 1031 ms 87032 KB Output is correct
30 Correct 2162 ms 179348 KB Output is correct
31 Correct 7792 ms 185716 KB Output is correct
32 Correct 7635 ms 185748 KB Output is correct
33 Correct 2134 ms 163192 KB Output is correct
34 Correct 7406 ms 182352 KB Output is correct
35 Correct 2142 ms 163068 KB Output is correct
36 Correct 7563 ms 182164 KB Output is correct
37 Correct 2231 ms 181300 KB Output is correct
38 Correct 7732 ms 186112 KB Output is correct
39 Correct 7 ms 8696 KB Output is correct
40 Correct 7854 ms 182432 KB Output is correct