oj.uz

Submission #126111

# Submission time Handle Problem Language Result Execution time Memory
126111 2019-07-07T05:09:33 Z nxteru Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 179012 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],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<<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 1320 ms 165308 KB Output is correct
2 Correct 1316 ms 165304 KB Output is correct
3 Correct 1387 ms 167752 KB Output is correct
4 Correct 1327 ms 165536 KB Output is correct
5 Correct 1319 ms 165576 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 6520 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 6420 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 22008 KB Output is correct
6 Correct 35 ms 22008 KB Output is correct
7 Correct 26 ms 22004 KB Output is correct
8 Correct 24 ms 21240 KB Output is correct
9 Correct 25 ms 22008 KB Output is correct
10 Correct 24 ms 21112 KB Output is correct
11 Correct 101 ms 23164 KB Output is correct
12 Correct 25 ms 22004 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 87876 KB Output is correct
2 Correct 522 ms 87032 KB Output is correct
3 Correct 620 ms 87788 KB Output is correct
4 Correct 612 ms 87752 KB Output is correct
5 Correct 604 ms 87160 KB Output is correct
6 Correct 7 ms 6520 KB Output is correct
7 Correct 7 ms 6524 KB Output is correct
8 Correct 7 ms 6520 KB Output is correct
9 Correct 1468 ms 87744 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 1319 ms 173496 KB Output is correct
2 Correct 1338 ms 173452 KB Output is correct
3 Correct 1338 ms 173268 KB Output is correct
4 Correct 1373 ms 174712 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 87728 KB Output is correct
2 Correct 520 ms 87032 KB Output is correct
3 Correct 618 ms 87928 KB Output is correct
4 Correct 617 ms 87800 KB Output is correct
5 Correct 601 ms 87160 KB Output is correct
6 Correct 1338 ms 173600 KB Output is correct
7 Correct 1348 ms 173304 KB Output is correct
8 Correct 1359 ms 173292 KB Output is correct
9 Correct 1396 ms 174712 KB Output is correct
10 Correct 1311 ms 165316 KB Output is correct
11 Correct 1325 ms 165236 KB Output is correct
12 Correct 1392 ms 167556 KB Output is correct
13 Correct 1331 ms 165264 KB Output is correct
14 Correct 1311 ms 165352 KB Output is correct
15 Correct 7 ms 6412 KB Output is correct
16 Correct 7 ms 6396 KB Output is correct
17 Correct 7 ms 6524 KB Output is correct
18 Correct 26 ms 22016 KB Output is correct
19 Correct 25 ms 22008 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 21112 KB Output is correct
23 Correct 25 ms 22008 KB Output is correct
24 Correct 25 ms 21112 KB Output is correct
25 Correct 103 ms 23696 KB Output is correct
26 Correct 25 ms 21980 KB Output is correct
27 Correct 1465 ms 87776 KB Output is correct
28 Correct 13061 ms 177332 KB Output is correct
29 Correct 12544 ms 161172 KB Output is correct
30 Correct 12642 ms 161212 KB Output is correct
31 Correct 13085 ms 178196 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 611 ms 87760 KB Output is correct
2 Correct 526 ms 86948 KB Output is correct
3 Correct 612 ms 87800 KB Output is correct
4 Correct 611 ms 87800 KB Output is correct
5 Correct 622 ms 86904 KB Output is correct
6 Correct 1332 ms 173432 KB Output is correct
7 Correct 1357 ms 173560 KB Output is correct
8 Correct 1378 ms 173564 KB Output is correct
9 Correct 1364 ms 174584 KB Output is correct
10 Correct 1318 ms 165432 KB Output is correct
11 Correct 1330 ms 165456 KB Output is correct
12 Correct 1387 ms 167360 KB Output is correct
13 Correct 1323 ms 165436 KB Output is correct
14 Correct 1328 ms 165472 KB Output is correct
15 Execution timed out 20040 ms 179012 KB Time limit exceeded
16 Halted 0 ms 0 KB -