oj.uz

Submission #126143

# Submission time Handle Problem Language Result Execution time Memory
126143 2019-07-07T06:02:00 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 176960 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;
SEG s;
void change(int x){
	x=x/B;
	node res;
	res.ini(m);
	for(int i=0;i<B&&x*B+i<n;i++){
		for(int j=0;j<m;j++){
			int *p=res.d[j];
			for(int k=1;k<m;k++)p[k]=min(p[k],p[k-1]+h[x*B+i][k-1]);
			for(int k=m-2;k>=0;k--)p[k]=min(p[k],p[k+1]+h[x*B+i][k]);
			for(int k=0;k<m;k++)p[k]+=w[x*B+i][k];
		}
	}
	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 807 ms 165240 KB Output is correct
2 Correct 817 ms 165180 KB Output is correct
3 Correct 926 ms 166776 KB Output is correct
4 Correct 826 ms 165112 KB Output is correct
5 Correct 808 ms 165240 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 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 23 ms 21624 KB Output is correct
5 Correct 22 ms 21672 KB Output is correct
6 Correct 22 ms 21624 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 22 ms 20856 KB Output is correct
11 Correct 98 ms 22648 KB Output is correct
12 Correct 23 ms 21672 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 86984 KB Output is correct
2 Correct 441 ms 86136 KB Output is correct
3 Correct 468 ms 86980 KB Output is correct
4 Correct 460 ms 86776 KB Output is correct
5 Correct 471 ms 86288 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 1178 ms 87024 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 820 ms 173220 KB Output is correct
2 Correct 831 ms 173180 KB Output is correct
3 Correct 867 ms 173176 KB Output is correct
4 Correct 879 ms 174072 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 87032 KB Output is correct
2 Correct 436 ms 86136 KB Output is correct
3 Correct 461 ms 86904 KB Output is correct
4 Correct 468 ms 86836 KB Output is correct
5 Correct 450 ms 86136 KB Output is correct
6 Correct 816 ms 173112 KB Output is correct
7 Correct 849 ms 173176 KB Output is correct
8 Correct 838 ms 173156 KB Output is correct
9 Correct 859 ms 174004 KB Output is correct
10 Correct 804 ms 165244 KB Output is correct
11 Correct 805 ms 165188 KB Output is correct
12 Correct 881 ms 166928 KB Output is correct
13 Correct 833 ms 165240 KB Output is correct
14 Correct 827 ms 165244 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 22 ms 21624 KB Output is correct
19 Correct 23 ms 21752 KB Output is correct
20 Correct 22 ms 21624 KB Output is correct
21 Correct 23 ms 21620 KB Output is correct
22 Correct 22 ms 20856 KB Output is correct
23 Correct 22 ms 21624 KB Output is correct
24 Correct 21 ms 20856 KB Output is correct
25 Correct 98 ms 22648 KB Output is correct
26 Correct 22 ms 21624 KB Output is correct
27 Correct 1170 ms 86948 KB Output is correct
28 Correct 10354 ms 175572 KB Output is correct
29 Correct 9051 ms 159336 KB Output is correct
30 Correct 9226 ms 159404 KB Output is correct
31 Correct 10385 ms 176556 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 452 ms 87032 KB Output is correct
2 Correct 431 ms 86104 KB Output is correct
3 Correct 461 ms 86904 KB Output is correct
4 Correct 459 ms 86904 KB Output is correct
5 Correct 451 ms 86156 KB Output is correct
6 Correct 836 ms 172996 KB Output is correct
7 Correct 857 ms 172980 KB Output is correct
8 Correct 844 ms 173128 KB Output is correct
9 Correct 861 ms 173864 KB Output is correct
10 Correct 806 ms 165032 KB Output is correct
11 Correct 806 ms 165036 KB Output is correct
12 Correct 880 ms 166664 KB Output is correct
13 Correct 822 ms 165132 KB Output is correct
14 Correct 806 ms 165116 KB Output is correct
15 Execution timed out 20079 ms 176960 KB Time limit exceeded
16 Halted 0 ms 0 KB -