oj.uz

Submission #126145

# Submission time Handle Problem Language Result Execution time Memory
126145 2019-07-07T06:03:11 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 97464 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
#define B 20
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<<9];
	void ini(int x){
		n=x;
		for(int i=0;i<1<<9;i++)seg[i].ini(n);
	}
	void up(int a,node &q){
		a+=(1<<8)-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 673 ms 86668 KB Output is correct
2 Correct 675 ms 86780 KB Output is correct
3 Correct 760 ms 88324 KB Output is correct
4 Correct 686 ms 86808 KB Output is correct
5 Correct 679 ms 86760 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 5 ms 3960 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3960 KB Output is correct
2 Correct 5 ms 3960 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 15 ms 11516 KB Output is correct
5 Correct 15 ms 11576 KB Output is correct
6 Correct 15 ms 11592 KB Output is correct
7 Correct 15 ms 11512 KB Output is correct
8 Correct 14 ms 11128 KB Output is correct
9 Correct 14 ms 11512 KB Output is correct
10 Correct 14 ms 11128 KB Output is correct
11 Correct 90 ms 12556 KB Output is correct
12 Correct 15 ms 11512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 44136 KB Output is correct
2 Correct 528 ms 43760 KB Output is correct
3 Correct 555 ms 44152 KB Output is correct
4 Correct 560 ms 44152 KB Output is correct
5 Correct 543 ms 43768 KB Output is correct
6 Correct 6 ms 3960 KB Output is correct
7 Correct 5 ms 3960 KB Output is correct
8 Correct 6 ms 3960 KB Output is correct
9 Correct 1557 ms 44152 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 94788 KB Output is correct
2 Correct 682 ms 94712 KB Output is correct
3 Correct 701 ms 94708 KB Output is correct
4 Correct 721 ms 95480 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 44084 KB Output is correct
2 Correct 525 ms 43768 KB Output is correct
3 Correct 553 ms 44192 KB Output is correct
4 Correct 553 ms 44304 KB Output is correct
5 Correct 546 ms 43872 KB Output is correct
6 Correct 683 ms 94692 KB Output is correct
7 Correct 684 ms 94756 KB Output is correct
8 Correct 710 ms 94788 KB Output is correct
9 Correct 729 ms 95604 KB Output is correct
10 Correct 674 ms 86696 KB Output is correct
11 Correct 680 ms 86784 KB Output is correct
12 Correct 748 ms 88428 KB Output is correct
13 Correct 692 ms 86792 KB Output is correct
14 Correct 688 ms 86836 KB Output is correct
15 Correct 5 ms 3960 KB Output is correct
16 Correct 5 ms 3960 KB Output is correct
17 Correct 5 ms 3960 KB Output is correct
18 Correct 13 ms 11512 KB Output is correct
19 Correct 15 ms 11512 KB Output is correct
20 Correct 17 ms 11512 KB Output is correct
21 Correct 15 ms 11512 KB Output is correct
22 Correct 14 ms 11140 KB Output is correct
23 Correct 14 ms 11512 KB Output is correct
24 Correct 14 ms 11128 KB Output is correct
25 Correct 91 ms 12652 KB Output is correct
26 Correct 16 ms 11512 KB Output is correct
27 Correct 1545 ms 44152 KB Output is correct
28 Correct 14025 ms 96232 KB Output is correct
29 Correct 12053 ms 86756 KB Output is correct
30 Correct 12180 ms 86944 KB Output is correct
31 Correct 14098 ms 97464 KB Output is correct
32 Correct 6 ms 5112 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 44236 KB Output is correct
2 Correct 555 ms 43868 KB Output is correct
3 Correct 560 ms 44280 KB Output is correct
4 Correct 562 ms 44264 KB Output is correct
5 Correct 551 ms 43808 KB Output is correct
6 Correct 694 ms 94912 KB Output is correct
7 Correct 686 ms 94940 KB Output is correct
8 Correct 702 ms 94840 KB Output is correct
9 Correct 729 ms 95528 KB Output is correct
10 Correct 668 ms 86904 KB Output is correct
11 Correct 677 ms 86680 KB Output is correct
12 Correct 750 ms 88592 KB Output is correct
13 Correct 694 ms 86820 KB Output is correct
14 Correct 682 ms 86904 KB Output is correct
15 Execution timed out 20057 ms 96732 KB Time limit exceeded
16 Halted 0 ms 0 KB -