oj.uz

Submission #126125

# Submission time Handle Problem Language Result Execution time Memory
126125 2019-07-07T05:35:26 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 178864 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[405][205],s;
		for(int i=n-1;i>-n;i--){
			int *b=a[i+n+1],*c=a[i+n];
			for(int j=max(-i,0);i+j<n&&j<n;j++){
				s=INF;
				int x,y;
				if(j-1>=0)x=b[j-1];
				else x=0;
				if(i+j+1<n)y=b[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];
					}
				}
				c[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[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 1316 ms 165296 KB Output is correct
2 Correct 1311 ms 165368 KB Output is correct
3 Correct 1396 ms 166972 KB Output is correct
4 Correct 1359 ms 165428 KB Output is correct
5 Correct 1332 ms 165376 KB Output is correct
6 Correct 7 ms 6520 KB Output is correct
7 Correct 7 ms 6380 KB Output is correct
8 Correct 7 ms 6396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6520 KB Output is correct
2 Correct 7 ms 6424 KB Output is correct
3 Correct 7 ms 6520 KB Output is correct
4 Correct 25 ms 22008 KB Output is correct
5 Correct 25 ms 21924 KB Output is correct
6 Correct 25 ms 22008 KB Output is correct
7 Correct 25 ms 21932 KB Output is correct
8 Correct 24 ms 21220 KB Output is correct
9 Correct 25 ms 22008 KB Output is correct
10 Correct 25 ms 21240 KB Output is correct
11 Correct 101 ms 23160 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 558 ms 87860 KB Output is correct
2 Correct 484 ms 87032 KB Output is correct
3 Correct 569 ms 87928 KB Output is correct
4 Correct 568 ms 87800 KB Output is correct
5 Correct 559 ms 86952 KB Output is correct
6 Correct 7 ms 6392 KB Output is correct
7 Correct 8 ms 6392 KB Output is correct
8 Correct 7 ms 6392 KB Output is correct
9 Correct 1359 ms 87920 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 1353 ms 173404 KB Output is correct
2 Correct 1330 ms 173388 KB Output is correct
3 Correct 1370 ms 173304 KB Output is correct
4 Correct 1408 ms 174344 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 87848 KB Output is correct
2 Correct 489 ms 87064 KB Output is correct
3 Correct 571 ms 87884 KB Output is correct
4 Correct 577 ms 87788 KB Output is correct
5 Correct 563 ms 87132 KB Output is correct
6 Correct 1329 ms 173312 KB Output is correct
7 Correct 1345 ms 173344 KB Output is correct
8 Correct 1361 ms 173336 KB Output is correct
9 Correct 1384 ms 174664 KB Output is correct
10 Correct 1352 ms 165356 KB Output is correct
11 Correct 1329 ms 165432 KB Output is correct
12 Correct 1407 ms 167792 KB Output is correct
13 Correct 1355 ms 165408 KB Output is correct
14 Correct 1324 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 7 ms 6520 KB Output is correct
18 Correct 25 ms 22008 KB Output is correct
19 Correct 25 ms 22008 KB Output is correct
20 Correct 25 ms 22036 KB Output is correct
21 Correct 25 ms 21960 KB Output is correct
22 Correct 24 ms 21112 KB Output is correct
23 Correct 25 ms 22008 KB Output is correct
24 Correct 25 ms 21116 KB Output is correct
25 Correct 102 ms 23928 KB Output is correct
26 Correct 25 ms 21980 KB Output is correct
27 Correct 1360 ms 87856 KB Output is correct
28 Correct 12039 ms 178144 KB Output is correct
29 Correct 11701 ms 162148 KB Output is correct
30 Correct 11721 ms 161988 KB Output is correct
31 Correct 12012 ms 178864 KB Output is correct
32 Correct 9 ms 8824 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 87900 KB Output is correct
2 Correct 497 ms 87072 KB Output is correct
3 Correct 575 ms 87984 KB Output is correct
4 Correct 575 ms 87840 KB Output is correct
5 Correct 567 ms 87076 KB Output is correct
6 Correct 1353 ms 173480 KB Output is correct
7 Correct 1376 ms 173268 KB Output is correct
8 Correct 1341 ms 173308 KB Output is correct
9 Correct 1377 ms 174748 KB Output is correct
10 Correct 1336 ms 165276 KB Output is correct
11 Correct 1351 ms 165260 KB Output is correct
12 Correct 1411 ms 166864 KB Output is correct
13 Correct 1351 ms 165348 KB Output is correct
14 Correct 1349 ms 165488 KB Output is correct
15 Execution timed out 20035 ms 178512 KB Time limit exceeded
16 Halted 0 ms 0 KB -