oj.uz

Submission #126148

# Submission time Handle Problem Language Result Execution time Memory
126148 2019-07-07T06:07:46 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 177096 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++){
			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++)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 802 ms 165144 KB Output is correct
2 Correct 855 ms 165248 KB Output is correct
3 Correct 889 ms 166760 KB Output is correct
4 Correct 836 ms 165172 KB Output is correct
5 Correct 840 ms 165200 KB Output is correct
6 Correct 8 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 7 ms 6264 KB Output is correct
2 Correct 6 ms 6264 KB Output is correct
3 Correct 7 ms 6264 KB Output is correct
4 Correct 22 ms 21724 KB Output is correct
5 Correct 22 ms 21752 KB Output is correct
6 Correct 22 ms 21752 KB Output is correct
7 Correct 22 ms 21624 KB Output is correct
8 Correct 21 ms 20856 KB Output is correct
9 Correct 22 ms 21624 KB Output is correct
10 Correct 21 ms 20856 KB Output is correct
11 Correct 98 ms 22652 KB Output is correct
12 Correct 26 ms 21624 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 86972 KB Output is correct
2 Correct 442 ms 86264 KB Output is correct
3 Correct 502 ms 87032 KB Output is correct
4 Correct 470 ms 86944 KB Output is correct
5 Correct 461 ms 86264 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 1198 ms 86964 KB Output is correct
10 Correct 10 ms 8696 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 173216 KB Output is correct
2 Correct 818 ms 173048 KB Output is correct
3 Correct 837 ms 173048 KB Output is correct
4 Correct 870 ms 174072 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 86984 KB Output is correct
2 Correct 444 ms 86136 KB Output is correct
3 Correct 468 ms 86876 KB Output is correct
4 Correct 479 ms 87060 KB Output is correct
5 Correct 469 ms 86136 KB Output is correct
6 Correct 813 ms 173176 KB Output is correct
7 Correct 818 ms 173188 KB Output is correct
8 Correct 837 ms 173048 KB Output is correct
9 Correct 850 ms 173856 KB Output is correct
10 Correct 810 ms 165344 KB Output is correct
11 Correct 814 ms 165240 KB Output is correct
12 Correct 874 ms 166776 KB Output is correct
13 Correct 823 ms 165324 KB Output is correct
14 Correct 807 ms 165240 KB Output is correct
15 Correct 6 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 22 ms 21624 KB Output is correct
19 Correct 22 ms 21624 KB Output is correct
20 Correct 22 ms 21624 KB Output is correct
21 Correct 22 ms 21624 KB Output is correct
22 Correct 21 ms 20856 KB Output is correct
23 Correct 22 ms 21624 KB Output is correct
24 Correct 22 ms 20856 KB Output is correct
25 Correct 98 ms 22648 KB Output is correct
26 Correct 22 ms 21752 KB Output is correct
27 Correct 1197 ms 86980 KB Output is correct
28 Correct 10522 ms 175480 KB Output is correct
29 Correct 9204 ms 159676 KB Output is correct
30 Correct 9479 ms 159600 KB Output is correct
31 Correct 10658 ms 176548 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 459 ms 86932 KB Output is correct
2 Correct 446 ms 86180 KB Output is correct
3 Correct 476 ms 86912 KB Output is correct
4 Correct 476 ms 86980 KB Output is correct
5 Correct 461 ms 86216 KB Output is correct
6 Correct 826 ms 173176 KB Output is correct
7 Correct 820 ms 173028 KB Output is correct
8 Correct 834 ms 173092 KB Output is correct
9 Correct 876 ms 173772 KB Output is correct
10 Correct 809 ms 165036 KB Output is correct
11 Correct 814 ms 165188 KB Output is correct
12 Correct 905 ms 166760 KB Output is correct
13 Correct 845 ms 165252 KB Output is correct
14 Correct 814 ms 165128 KB Output is correct
15 Execution timed out 20094 ms 177096 KB Time limit exceeded
16 Halted 0 ms 0 KB -