oj.uz

Submission #126142

# Submission time Handle Problem Language Result Execution time Memory
126142 2019-07-07T05:58:48 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 177272 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;
node res[B];
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++){
			for(int k=1;k<m;k++)p[j][k]=min(p[j][k],p[j][k-1]+h[x*B+i][k-1]);
			for(int k=m-2;k>=0;k--)p[j][k]=min(p[j][k],p[j][k+1]+h[x*B+i][k]);
			for(int k=0;k<m;k++)p[j][k]+=w[x*B+i][k];
		}
	}
	node res;
	res.ini(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++)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 814 ms 165112 KB Output is correct
2 Correct 831 ms 165240 KB Output is correct
3 Correct 879 ms 166728 KB Output is correct
4 Correct 846 ms 165264 KB Output is correct
5 Correct 815 ms 165240 KB Output is correct
6 Correct 7 ms 6356 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 7 ms 6264 KB Output is correct
2 Correct 7 ms 6268 KB Output is correct
3 Correct 7 ms 6268 KB Output is correct
4 Correct 23 ms 21752 KB Output is correct
5 Correct 22 ms 21624 KB Output is correct
6 Correct 23 ms 21752 KB Output is correct
7 Correct 22 ms 21752 KB Output is correct
8 Correct 22 ms 20856 KB Output is correct
9 Correct 22 ms 21624 KB Output is correct
10 Correct 22 ms 20984 KB Output is correct
11 Correct 98 ms 22652 KB Output is correct
12 Correct 22 ms 21752 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 87032 KB Output is correct
2 Correct 455 ms 86312 KB Output is correct
3 Correct 474 ms 87032 KB Output is correct
4 Correct 488 ms 86904 KB Output is correct
5 Correct 490 ms 86308 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
9 Correct 1230 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 826 ms 173036 KB Output is correct
2 Correct 855 ms 173052 KB Output is correct
3 Correct 843 ms 173212 KB Output is correct
4 Correct 854 ms 173944 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 86908 KB Output is correct
2 Correct 451 ms 86136 KB Output is correct
3 Correct 473 ms 87088 KB Output is correct
4 Correct 472 ms 86964 KB Output is correct
5 Correct 464 ms 86136 KB Output is correct
6 Correct 819 ms 173068 KB Output is correct
7 Correct 815 ms 173076 KB Output is correct
8 Correct 835 ms 173048 KB Output is correct
9 Correct 854 ms 174220 KB Output is correct
10 Correct 803 ms 165260 KB Output is correct
11 Correct 811 ms 165260 KB Output is correct
12 Correct 896 ms 166676 KB Output is correct
13 Correct 823 ms 165232 KB Output is correct
14 Correct 808 ms 165084 KB Output is correct
15 Correct 7 ms 6264 KB Output is correct
16 Correct 7 ms 6264 KB Output is correct
17 Correct 7 ms 6264 KB Output is correct
18 Correct 23 ms 21624 KB Output is correct
19 Correct 22 ms 21752 KB Output is correct
20 Correct 22 ms 21752 KB Output is correct
21 Correct 23 ms 21752 KB Output is correct
22 Correct 22 ms 20856 KB Output is correct
23 Correct 22 ms 21752 KB Output is correct
24 Correct 22 ms 20856 KB Output is correct
25 Correct 99 ms 22648 KB Output is correct
26 Correct 23 ms 21756 KB Output is correct
27 Correct 1225 ms 87132 KB Output is correct
28 Correct 10649 ms 175728 KB Output is correct
29 Correct 9301 ms 159528 KB Output is correct
30 Correct 9435 ms 159500 KB Output is correct
31 Correct 10749 ms 176684 KB Output is correct
32 Correct 9 ms 8696 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 86896 KB Output is correct
2 Correct 443 ms 86264 KB Output is correct
3 Correct 475 ms 86984 KB Output is correct
4 Correct 474 ms 87032 KB Output is correct
5 Correct 469 ms 86264 KB Output is correct
6 Correct 843 ms 173156 KB Output is correct
7 Correct 820 ms 173200 KB Output is correct
8 Correct 842 ms 173148 KB Output is correct
9 Correct 872 ms 174012 KB Output is correct
10 Correct 900 ms 165216 KB Output is correct
11 Correct 830 ms 165188 KB Output is correct
12 Correct 887 ms 166776 KB Output is correct
13 Correct 826 ms 165128 KB Output is correct
14 Correct 811 ms 165240 KB Output is correct
15 Execution timed out 20051 ms 177272 KB Time limit exceeded
16 Halted 0 ms 0 KB -