oj.uz

Submission #126149

# Submission time Handle Problem Language Result Execution time Memory
126149 2019-07-07T06:08:49 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 177052 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++)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 809 ms 165112 KB Output is correct
2 Correct 812 ms 165128 KB Output is correct
3 Correct 883 ms 166704 KB Output is correct
4 Correct 827 ms 165100 KB Output is correct
5 Correct 802 ms 165188 KB Output is correct
6 Correct 7 ms 6264 KB Output is correct
7 Correct 7 ms 6272 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 6264 KB Output is correct
3 Correct 7 ms 6264 KB Output is correct
4 Correct 22 ms 21624 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 21624 KB Output is correct
8 Correct 21 ms 20856 KB Output is correct
9 Correct 22 ms 21752 KB Output is correct
10 Correct 21 ms 20856 KB Output is correct
11 Correct 106 ms 22668 KB Output is correct
12 Correct 23 ms 21736 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 86908 KB Output is correct
2 Correct 455 ms 86344 KB Output is correct
3 Correct 481 ms 87020 KB Output is correct
4 Correct 469 ms 86996 KB Output is correct
5 Correct 461 ms 86208 KB Output is correct
6 Correct 7 ms 6264 KB Output is correct
7 Correct 7 ms 6268 KB Output is correct
8 Correct 7 ms 6268 KB Output is correct
9 Correct 1209 ms 86996 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 819 ms 173108 KB Output is correct
2 Correct 827 ms 173124 KB Output is correct
3 Correct 838 ms 173064 KB Output is correct
4 Correct 858 ms 173884 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 87032 KB Output is correct
2 Correct 442 ms 86240 KB Output is correct
3 Correct 469 ms 86916 KB Output is correct
4 Correct 469 ms 86988 KB Output is correct
5 Correct 461 ms 86236 KB Output is correct
6 Correct 818 ms 172952 KB Output is correct
7 Correct 824 ms 173052 KB Output is correct
8 Correct 835 ms 173272 KB Output is correct
9 Correct 878 ms 173816 KB Output is correct
10 Correct 811 ms 165240 KB Output is correct
11 Correct 805 ms 165240 KB Output is correct
12 Correct 878 ms 166780 KB Output is correct
13 Correct 824 ms 165176 KB Output is correct
14 Correct 804 ms 165240 KB Output is correct
15 Correct 7 ms 6264 KB Output is correct
16 Correct 7 ms 6224 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 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 101 ms 22816 KB Output is correct
26 Correct 22 ms 21624 KB Output is correct
27 Correct 1202 ms 87064 KB Output is correct
28 Correct 10662 ms 175480 KB Output is correct
29 Correct 9230 ms 159624 KB Output is correct
30 Correct 9382 ms 159376 KB Output is correct
31 Correct 10765 ms 176444 KB Output is correct
32 Correct 11 ms 8696 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 87092 KB Output is correct
2 Correct 448 ms 86264 KB Output is correct
3 Correct 469 ms 86980 KB Output is correct
4 Correct 472 ms 86904 KB Output is correct
5 Correct 467 ms 86136 KB Output is correct
6 Correct 823 ms 173048 KB Output is correct
7 Correct 820 ms 173120 KB Output is correct
8 Correct 851 ms 173208 KB Output is correct
9 Correct 865 ms 173820 KB Output is correct
10 Correct 814 ms 165152 KB Output is correct
11 Correct 803 ms 165164 KB Output is correct
12 Correct 885 ms 166664 KB Output is correct
13 Correct 820 ms 165048 KB Output is correct
14 Correct 810 ms 165092 KB Output is correct
15 Execution timed out 20103 ms 177052 KB Time limit exceeded
16 Halted 0 ms 0 KB -