oj.uz

Submission #126116

# Submission time Handle Problem Language Result Execution time Memory
126116 2019-07-07T05:23:28 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 179404 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[B][205];
SEG s;
node res[B];
void change(int x){
	x=x/B;
	for(int i=0;i<B&&x*B+i<n;i++)p[i][0]=0,res[i].ini(m);
	for(int i=0;i<B&&x*B+i<n;i++)for(int j=1;j<m;j++)p[i][j]=p[i][j-1]+h[x*B+i][j-1];
	for(int i=0;i<B&&x*B+i<n;i++){
		int *y=p[i],*z=w[x*B+i];
		for(int j=0;j<m;j++){
			for(int k=0;k<m;k++){
				res[i].d[j][k]=y[max(j,k)]-y[min(j,k)]+z[k];
			}
		}
	}
	for(int i=1;i<B&&x*B+i<n;i++)res[0]=res[0].plus(res[i]);
	s.up(x,res[0]);
}
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++)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 1313 ms 165312 KB Output is correct
2 Correct 1322 ms 165384 KB Output is correct
3 Correct 1395 ms 167228 KB Output is correct
4 Correct 1323 ms 165496 KB Output is correct
5 Correct 1326 ms 165512 KB Output is correct
6 Correct 7 ms 6392 KB Output is correct
7 Correct 7 ms 6520 KB Output is correct
8 Correct 7 ms 6392 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6392 KB Output is correct
2 Correct 7 ms 6392 KB Output is correct
3 Correct 7 ms 6392 KB Output is correct
4 Correct 25 ms 22008 KB Output is correct
5 Correct 25 ms 21992 KB Output is correct
6 Correct 25 ms 22008 KB Output is correct
7 Correct 25 ms 22008 KB Output is correct
8 Correct 24 ms 21112 KB Output is correct
9 Correct 25 ms 22008 KB Output is correct
10 Correct 24 ms 21240 KB Output is correct
11 Correct 102 ms 23212 KB Output is correct
12 Correct 25 ms 22008 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 87768 KB Output is correct
2 Correct 518 ms 87024 KB Output is correct
3 Correct 609 ms 88008 KB Output is correct
4 Correct 609 ms 87772 KB Output is correct
5 Correct 596 ms 87176 KB Output is correct
6 Correct 7 ms 6392 KB Output is correct
7 Correct 8 ms 6520 KB Output is correct
8 Correct 7 ms 6392 KB Output is correct
9 Correct 1457 ms 87884 KB Output is correct
10 Correct 9 ms 8824 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1339 ms 173600 KB Output is correct
2 Correct 1341 ms 173308 KB Output is correct
3 Correct 1345 ms 173624 KB Output is correct
4 Correct 1362 ms 174264 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 87800 KB Output is correct
2 Correct 529 ms 87160 KB Output is correct
3 Correct 625 ms 87876 KB Output is correct
4 Correct 609 ms 87928 KB Output is correct
5 Correct 596 ms 87040 KB Output is correct
6 Correct 1321 ms 173432 KB Output is correct
7 Correct 1324 ms 173356 KB Output is correct
8 Correct 1384 ms 173432 KB Output is correct
9 Correct 1360 ms 174220 KB Output is correct
10 Correct 1336 ms 165524 KB Output is correct
11 Correct 1329 ms 165368 KB Output is correct
12 Correct 1395 ms 166956 KB Output is correct
13 Correct 1320 ms 165368 KB Output is correct
14 Correct 1335 ms 165464 KB Output is correct
15 Correct 7 ms 6392 KB Output is correct
16 Correct 7 ms 6520 KB Output is correct
17 Correct 7 ms 6520 KB Output is correct
18 Correct 25 ms 22008 KB Output is correct
19 Correct 25 ms 22008 KB Output is correct
20 Correct 25 ms 22008 KB Output is correct
21 Correct 24 ms 22008 KB Output is correct
22 Correct 24 ms 21112 KB Output is correct
23 Correct 24 ms 22008 KB Output is correct
24 Correct 24 ms 21112 KB Output is correct
25 Correct 101 ms 23032 KB Output is correct
26 Correct 25 ms 22008 KB Output is correct
27 Correct 1465 ms 87644 KB Output is correct
28 Correct 13013 ms 176428 KB Output is correct
29 Correct 12434 ms 160284 KB Output is correct
30 Correct 12562 ms 160268 KB Output is correct
31 Correct 13012 ms 177448 KB Output is correct
32 Correct 9 ms 8824 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 87788 KB Output is correct
2 Correct 521 ms 87032 KB Output is correct
3 Correct 608 ms 87700 KB Output is correct
4 Correct 608 ms 87732 KB Output is correct
5 Correct 603 ms 87016 KB Output is correct
6 Correct 1329 ms 173396 KB Output is correct
7 Correct 1357 ms 173304 KB Output is correct
8 Correct 1362 ms 173384 KB Output is correct
9 Correct 1387 ms 174108 KB Output is correct
10 Correct 1306 ms 165372 KB Output is correct
11 Correct 1326 ms 165268 KB Output is correct
12 Correct 1393 ms 167772 KB Output is correct
13 Correct 1353 ms 165284 KB Output is correct
14 Correct 1336 ms 165240 KB Output is correct
15 Execution timed out 20039 ms 179404 KB Time limit exceeded
16 Halted 0 ms 0 KB -