oj.uz

Submission #126100

# Submission time Handle Problem Language Result Execution time Memory
126100 2019-07-07T03:43:33 Z nxteru Wombats (IOI13_wombats) C++14
28 / 100
 1581 ms 262148 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
#define B 5
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<<11];
	void ini(int x){
		n=x;
		for(int i=0;i<1<<11;i++)seg[i].ini(n);
	}
	void up(int a,node &q){
		a+=(1<<10)-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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 909 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11000 KB Output is correct
2 Correct 11 ms 11000 KB Output is correct
3 Correct 12 ms 11076 KB Output is correct
4 Correct 40 ms 42108 KB Output is correct
5 Correct 40 ms 42172 KB Output is correct
6 Correct 41 ms 42104 KB Output is correct
7 Correct 40 ms 42104 KB Output is correct
8 Correct 39 ms 40696 KB Output is correct
9 Correct 40 ms 42104 KB Output is correct
10 Correct 39 ms 40568 KB Output is correct
11 Correct 116 ms 43384 KB Output is correct
12 Correct 40 ms 42104 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 173024 KB Output is correct
2 Correct 611 ms 171380 KB Output is correct
3 Correct 685 ms 172968 KB Output is correct
4 Correct 681 ms 172920 KB Output is correct
5 Correct 666 ms 171256 KB Output is correct
6 Correct 10 ms 11000 KB Output is correct
7 Correct 10 ms 11016 KB Output is correct
8 Correct 10 ms 11000 KB Output is correct
9 Correct 1581 ms 172900 KB Output is correct
10 Correct 14 ms 15864 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 897 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 172784 KB Output is correct
2 Correct 620 ms 171384 KB Output is correct
3 Correct 688 ms 172920 KB Output is correct
4 Correct 678 ms 172792 KB Output is correct
5 Correct 666 ms 171376 KB Output is correct
6 Runtime error 898 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 172824 KB Output is correct
2 Correct 617 ms 171236 KB Output is correct
3 Correct 683 ms 172852 KB Output is correct
4 Correct 680 ms 172800 KB Output is correct
5 Correct 667 ms 171292 KB Output is correct
6 Runtime error 881 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -