oj.uz

Submission #126098

# Submission time Handle Problem Language Result Execution time Memory
126098 2019-07-07T03:42:26 Z nxteru Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 100600 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
#define B 20
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<<9];
	void ini(int x){
		n=x;
		for(int i=0;i<1<<9;i++)seg[i].ini(n);
	}
	void up(int a,node &q){
		a+=(1<<8)-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 1745 ms 87108 KB Output is correct
2 Correct 1734 ms 87112 KB Output is correct
3 Correct 1796 ms 88812 KB Output is correct
4 Correct 1775 ms 87056 KB Output is correct
5 Correct 1751 ms 87160 KB Output is correct
6 Correct 5 ms 4092 KB Output is correct
7 Correct 5 ms 4088 KB Output is correct
8 Correct 5 ms 4088 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4116 KB Output is correct
2 Correct 5 ms 4088 KB Output is correct
3 Correct 5 ms 4088 KB Output is correct
4 Correct 22 ms 12124 KB Output is correct
5 Correct 21 ms 12024 KB Output is correct
6 Correct 24 ms 12060 KB Output is correct
7 Correct 24 ms 12152 KB Output is correct
8 Correct 21 ms 11640 KB Output is correct
9 Correct 21 ms 12024 KB Output is correct
10 Correct 21 ms 11640 KB Output is correct
11 Correct 99 ms 13176 KB Output is correct
12 Correct 21 ms 12152 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1150 ms 45940 KB Output is correct
2 Correct 985 ms 45600 KB Output is correct
3 Correct 1181 ms 45892 KB Output is correct
4 Correct 1193 ms 45816 KB Output is correct
5 Correct 1149 ms 45656 KB Output is correct
6 Correct 5 ms 4088 KB Output is correct
7 Correct 5 ms 4088 KB Output is correct
8 Correct 5 ms 4088 KB Output is correct
9 Correct 2981 ms 46048 KB Output is correct
10 Correct 6 ms 5368 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1804 ms 95260 KB Output is correct
2 Correct 1758 ms 95120 KB Output is correct
3 Correct 1838 ms 95352 KB Output is correct
4 Correct 1843 ms 96048 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1132 ms 45968 KB Output is correct
2 Correct 998 ms 45560 KB Output is correct
3 Correct 1167 ms 45816 KB Output is correct
4 Correct 1174 ms 45992 KB Output is correct
5 Correct 1144 ms 45560 KB Output is correct
6 Correct 1752 ms 95156 KB Output is correct
7 Correct 1730 ms 95068 KB Output is correct
8 Correct 1787 ms 95128 KB Output is correct
9 Correct 1781 ms 96188 KB Output is correct
10 Correct 1852 ms 87192 KB Output is correct
11 Correct 1726 ms 87264 KB Output is correct
12 Correct 1794 ms 89084 KB Output is correct
13 Correct 1737 ms 87140 KB Output is correct
14 Correct 1734 ms 87032 KB Output is correct
15 Correct 5 ms 4088 KB Output is correct
16 Correct 6 ms 4088 KB Output is correct
17 Correct 6 ms 4088 KB Output is correct
18 Correct 22 ms 12024 KB Output is correct
19 Correct 21 ms 12024 KB Output is correct
20 Correct 21 ms 12024 KB Output is correct
21 Correct 21 ms 12024 KB Output is correct
22 Correct 20 ms 11640 KB Output is correct
23 Correct 22 ms 12024 KB Output is correct
24 Correct 21 ms 11640 KB Output is correct
25 Correct 99 ms 13440 KB Output is correct
26 Correct 21 ms 12024 KB Output is correct
27 Correct 3018 ms 45880 KB Output is correct
28 Execution timed out 20035 ms 91136 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 45892 KB Output is correct
2 Correct 986 ms 45544 KB Output is correct
3 Correct 1157 ms 45880 KB Output is correct
4 Correct 1168 ms 45836 KB Output is correct
5 Correct 1183 ms 45552 KB Output is correct
6 Correct 1746 ms 94944 KB Output is correct
7 Correct 1772 ms 95056 KB Output is correct
8 Correct 1761 ms 94936 KB Output is correct
9 Correct 1810 ms 96348 KB Output is correct
10 Correct 1792 ms 87164 KB Output is correct
11 Correct 1783 ms 87164 KB Output is correct
12 Correct 1849 ms 89264 KB Output is correct
13 Correct 1742 ms 87160 KB Output is correct
14 Correct 1737 ms 87160 KB Output is correct
15 Execution timed out 20092 ms 100600 KB Time limit exceeded
16 Halted 0 ms 0 KB -