oj.uz

Submission #126127

# Submission time Handle Problem Language Result Execution time Memory
126127 2019-07-07T05:36:56 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 178552 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,z=i+j;
				if(j-1>=0)x=b[j-1];
				else x=0;
				if(z+1<n)y=b[j];
				else y=n-1;
				for(int k=x;k<=y;k++){
					if(d[z][k]+q.d[k][j]<s){
						x=k;
						s=d[z][k]+q.d[k][j];
					}
				}
				c[j]=x;
				res.d[z][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 1330 ms 165236 KB Output is correct
2 Correct 1316 ms 165348 KB Output is correct
3 Correct 1404 ms 167860 KB Output is correct
4 Correct 1340 ms 165356 KB Output is correct
5 Correct 1332 ms 165296 KB Output is correct
6 Correct 7 ms 6392 KB Output is correct
7 Correct 7 ms 6392 KB Output is correct
8 Correct 7 ms 6392 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6392 KB Output is correct
2 Correct 7 ms 6392 KB Output is correct
3 Correct 7 ms 6392 KB Output is correct
4 Correct 25 ms 22008 KB Output is correct
5 Correct 25 ms 22060 KB Output is correct
6 Correct 25 ms 22008 KB Output is correct
7 Correct 25 ms 22012 KB Output is correct
8 Correct 24 ms 21112 KB Output is correct
9 Correct 25 ms 22136 KB Output is correct
10 Correct 25 ms 21112 KB Output is correct
11 Correct 102 ms 24028 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 561 ms 87928 KB Output is correct
2 Correct 483 ms 87056 KB Output is correct
3 Correct 575 ms 87928 KB Output is correct
4 Correct 570 ms 87800 KB Output is correct
5 Correct 562 ms 87044 KB Output is correct
6 Correct 7 ms 6392 KB Output is correct
7 Correct 7 ms 6520 KB Output is correct
8 Correct 7 ms 6524 KB Output is correct
9 Correct 1342 ms 87864 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 1333 ms 173408 KB Output is correct
2 Correct 1363 ms 173444 KB Output is correct
3 Correct 1350 ms 173344 KB Output is correct
4 Correct 1412 ms 174808 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 87788 KB Output is correct
2 Correct 496 ms 86980 KB Output is correct
3 Correct 576 ms 87800 KB Output is correct
4 Correct 575 ms 87928 KB Output is correct
5 Correct 563 ms 87152 KB Output is correct
6 Correct 1331 ms 173340 KB Output is correct
7 Correct 1366 ms 173400 KB Output is correct
8 Correct 1354 ms 173412 KB Output is correct
9 Correct 1386 ms 174096 KB Output is correct
10 Correct 1327 ms 165500 KB Output is correct
11 Correct 1313 ms 165240 KB Output is correct
12 Correct 1388 ms 167168 KB Output is correct
13 Correct 1338 ms 165392 KB Output is correct
14 Correct 1344 ms 165340 KB Output is correct
15 Correct 7 ms 6392 KB Output is correct
16 Correct 7 ms 6392 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 22008 KB Output is correct
21 Correct 30 ms 22008 KB Output is correct
22 Correct 24 ms 21112 KB Output is correct
23 Correct 25 ms 21984 KB Output is correct
24 Correct 29 ms 21112 KB Output is correct
25 Correct 102 ms 23032 KB Output is correct
26 Correct 25 ms 22008 KB Output is correct
27 Correct 1355 ms 87780 KB Output is correct
28 Correct 12002 ms 176308 KB Output is correct
29 Correct 11658 ms 160364 KB Output is correct
30 Correct 11710 ms 160160 KB Output is correct
31 Correct 12058 ms 177404 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 562 ms 87868 KB Output is correct
2 Correct 483 ms 87032 KB Output is correct
3 Correct 588 ms 87888 KB Output is correct
4 Correct 592 ms 87840 KB Output is correct
5 Correct 567 ms 86936 KB Output is correct
6 Correct 1334 ms 173376 KB Output is correct
7 Correct 1343 ms 173304 KB Output is correct
8 Correct 1345 ms 173312 KB Output is correct
9 Correct 1388 ms 174232 KB Output is correct
10 Correct 1360 ms 165496 KB Output is correct
11 Correct 1328 ms 165424 KB Output is correct
12 Correct 1411 ms 166856 KB Output is correct
13 Correct 1350 ms 165416 KB Output is correct
14 Correct 1316 ms 165268 KB Output is correct
15 Execution timed out 20042 ms 178552 KB Time limit exceeded
16 Halted 0 ms 0 KB -