oj.uz

Submission #126123

# Submission time Handle Problem Language Result Execution time Memory
126123 2019-07-07T05:34:11 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 182524 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--){
			for(int j=max(-i,0);i+j<n&&j<n;j++){
				s=INF;
				int x,y;
				if(j-1>=0)x=a[i+n+1][j-1];
				else x=0;
				if(i+j+1<n)y=a[i+n+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+n][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 1342 ms 165292 KB Output is correct
2 Correct 1330 ms 165348 KB Output is correct
3 Correct 1411 ms 167100 KB Output is correct
4 Correct 1330 ms 165368 KB Output is correct
5 Correct 1323 ms 165368 KB Output is correct
6 Correct 7 ms 6520 KB Output is correct
7 Correct 7 ms 6456 KB Output is correct
8 Correct 7 ms 6524 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 6520 KB Output is correct
4 Correct 25 ms 22136 KB Output is correct
5 Correct 25 ms 21980 KB Output is correct
6 Correct 26 ms 22008 KB Output is correct
7 Correct 25 ms 22008 KB Output is correct
8 Correct 24 ms 21240 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 24032 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 572 ms 87916 KB Output is correct
2 Correct 488 ms 87032 KB Output is correct
3 Correct 595 ms 88068 KB Output is correct
4 Correct 587 ms 88056 KB Output is correct
5 Correct 572 ms 87032 KB Output is correct
6 Correct 7 ms 6520 KB Output is correct
7 Correct 7 ms 6392 KB Output is correct
8 Correct 7 ms 6520 KB Output is correct
9 Correct 1369 ms 87964 KB Output is correct
10 Correct 9 ms 8952 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1340 ms 173424 KB Output is correct
2 Correct 1381 ms 173356 KB Output is correct
3 Correct 1350 ms 173348 KB Output is correct
4 Correct 1386 ms 174732 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 87868 KB Output is correct
2 Correct 491 ms 86976 KB Output is correct
3 Correct 593 ms 87928 KB Output is correct
4 Correct 590 ms 87848 KB Output is correct
5 Correct 576 ms 87232 KB Output is correct
6 Correct 1361 ms 173320 KB Output is correct
7 Correct 1347 ms 173432 KB Output is correct
8 Correct 1341 ms 173396 KB Output is correct
9 Correct 1385 ms 174748 KB Output is correct
10 Correct 1319 ms 165424 KB Output is correct
11 Correct 1323 ms 165500 KB Output is correct
12 Correct 1409 ms 168204 KB Output is correct
13 Correct 1342 ms 165496 KB Output is correct
14 Correct 1339 ms 165396 KB Output is correct
15 Correct 7 ms 6520 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 22080 KB Output is correct
20 Correct 25 ms 22008 KB Output is correct
21 Correct 25 ms 22008 KB Output is correct
22 Correct 24 ms 21244 KB Output is correct
23 Correct 25 ms 22008 KB Output is correct
24 Correct 25 ms 21244 KB Output is correct
25 Correct 102 ms 24312 KB Output is correct
26 Correct 25 ms 22008 KB Output is correct
27 Correct 1361 ms 87772 KB Output is correct
28 Correct 12131 ms 177824 KB Output is correct
29 Correct 11912 ms 161560 KB Output is correct
30 Correct 11973 ms 161532 KB Output is correct
31 Correct 12265 ms 178848 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 583 ms 87932 KB Output is correct
2 Correct 491 ms 87064 KB Output is correct
3 Correct 583 ms 87996 KB Output is correct
4 Correct 598 ms 87884 KB Output is correct
5 Correct 574 ms 87112 KB Output is correct
6 Correct 1335 ms 173344 KB Output is correct
7 Correct 1334 ms 173208 KB Output is correct
8 Correct 1361 ms 173384 KB Output is correct
9 Correct 1371 ms 174692 KB Output is correct
10 Correct 1337 ms 165340 KB Output is correct
11 Correct 1356 ms 165448 KB Output is correct
12 Correct 1419 ms 168024 KB Output is correct
13 Correct 1340 ms 165316 KB Output is correct
14 Correct 1357 ms 165320 KB Output is correct
15 Execution timed out 20091 ms 182524 KB Time limit exceeded
16 Halted 0 ms 0 KB -