oj.uz

Submission #126097

# Submission time Handle Problem Language Result Execution time Memory
126097 2019-07-07T03:38:08 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 181756 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];
		for(int i=n-1;i>-n;i--){
			for(int j=max(-i,0);i+j<n&&j<n;j++){
				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]<d[i+j][x]+q.d[x][j])x=k;
				a[i+j][j]=x;
				res.d[i+j][j]=min(d[i+j][x]+q.d[x][j],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[B][205];
SEG s;
node res[B];
void change(int x){
	x=x/B;
	for(int i=0;i<B&&x*B+i<n;i++)p[i][0]=0,res[i].ini(m);
	for(int i=0;i<B&&x*B+i<n;i++)for(int j=1;j<m;j++)p[i][j]=p[i][j-1]+h[x*B+i][j-1];
	for(int i=0;i<B&&x*B+i<n;i++){
		for(int j=0;j<m;j++){
			for(int k=0;k<m;k++){
				res[i].d[j][k]=p[i][max(j,k)]-p[i][min(j,k)]+w[x*B+i][k];
			}
		}
	}
	for(int i=1;i<B&&x*B+i<n;i++)res[0]=res[0].plus(res[i]);
	s.up(x,res[0]);
}
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 1317 ms 165464 KB Output is correct
2 Correct 1330 ms 165412 KB Output is correct
3 Correct 1380 ms 168144 KB Output is correct
4 Correct 1342 ms 165320 KB Output is correct
5 Correct 1319 ms 165456 KB Output is correct
6 Correct 7 ms 6520 KB Output is correct
7 Correct 7 ms 6520 KB Output is correct
8 Correct 7 ms 6520 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6396 KB Output is correct
2 Correct 7 ms 6392 KB Output is correct
3 Correct 7 ms 6520 KB Output is correct
4 Correct 26 ms 21920 KB Output is correct
5 Correct 25 ms 22008 KB Output is correct
6 Correct 25 ms 22008 KB Output is correct
7 Correct 26 ms 22008 KB Output is correct
8 Correct 24 ms 21112 KB Output is correct
9 Correct 25 ms 22008 KB Output is correct
10 Correct 25 ms 21112 KB Output is correct
11 Correct 102 ms 23032 KB Output is correct
12 Correct 25 ms 22008 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 87764 KB Output is correct
2 Correct 695 ms 86876 KB Output is correct
3 Correct 798 ms 87792 KB Output is correct
4 Correct 803 ms 87792 KB Output is correct
5 Correct 788 ms 87168 KB Output is correct
6 Correct 7 ms 6520 KB Output is correct
7 Correct 6 ms 6520 KB Output is correct
8 Correct 6 ms 6520 KB Output is correct
9 Correct 1983 ms 87800 KB Output is correct
10 Correct 9 ms 8824 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1342 ms 173560 KB Output is correct
2 Correct 1345 ms 173304 KB Output is correct
3 Correct 1348 ms 173432 KB Output is correct
4 Correct 1363 ms 174832 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 87764 KB Output is correct
2 Correct 698 ms 86968 KB Output is correct
3 Correct 798 ms 87672 KB Output is correct
4 Correct 801 ms 87800 KB Output is correct
5 Correct 850 ms 87032 KB Output is correct
6 Correct 1337 ms 173568 KB Output is correct
7 Correct 1323 ms 173564 KB Output is correct
8 Correct 1361 ms 173460 KB Output is correct
9 Correct 1372 ms 174628 KB Output is correct
10 Correct 1311 ms 165496 KB Output is correct
11 Correct 1310 ms 165508 KB Output is correct
12 Correct 1383 ms 168184 KB Output is correct
13 Correct 1331 ms 165400 KB Output is correct
14 Correct 1353 ms 165368 KB Output is correct
15 Correct 7 ms 6392 KB Output is correct
16 Correct 7 ms 6520 KB Output is correct
17 Correct 8 ms 6392 KB Output is correct
18 Correct 26 ms 22008 KB Output is correct
19 Correct 26 ms 22008 KB Output is correct
20 Correct 26 ms 22008 KB Output is correct
21 Correct 26 ms 22008 KB Output is correct
22 Correct 24 ms 21112 KB Output is correct
23 Correct 30 ms 22008 KB Output is correct
24 Correct 25 ms 21240 KB Output is correct
25 Correct 102 ms 24412 KB Output is correct
26 Correct 26 ms 21980 KB Output is correct
27 Correct 1999 ms 87932 KB Output is correct
28 Correct 17691 ms 180040 KB Output is correct
29 Correct 16658 ms 163692 KB Output is correct
30 Correct 16795 ms 163768 KB Output is correct
31 Correct 18095 ms 181752 KB Output is correct
32 Correct 11 ms 8824 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 87800 KB Output is correct
2 Correct 701 ms 87132 KB Output is correct
3 Correct 809 ms 87928 KB Output is correct
4 Correct 809 ms 87800 KB Output is correct
5 Correct 783 ms 87032 KB Output is correct
6 Correct 1365 ms 173344 KB Output is correct
7 Correct 1370 ms 173424 KB Output is correct
8 Correct 1361 ms 173380 KB Output is correct
9 Correct 1383 ms 174872 KB Output is correct
10 Correct 1358 ms 165320 KB Output is correct
11 Correct 1350 ms 165596 KB Output is correct
12 Correct 1394 ms 168164 KB Output is correct
13 Correct 1332 ms 165412 KB Output is correct
14 Correct 1360 ms 165320 KB Output is correct
15 Execution timed out 20031 ms 181756 KB Time limit exceeded
16 Halted 0 ms 0 KB -