oj.uz

Submission #126093

# Submission time Handle Problem Language Result Execution time Memory
126093 2019-07-07T03:20:45 Z nxteru Wombats (IOI13_wombats) C++14
12 / 100
 336 ms 262148 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
struct node{
	int n,d[100][100];
	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[100][100];
		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,k,id[1<<14];
	node seg[10011];
	void ini(int x){
		n=x;
		for(int i=0;i<1<<14;i++)id[i]=-1;
		k=0;
		for(int i=0;i<5000;i++){
			int a=i+(1<<13)-1;
			if(id[a]==-1)id[a]=k++;
			while(a>0){
				a=(a-1)/2;
				if(id[a]==-1)id[a]=k++;
				if(id[a*2+1]==-1)id[a*2+1]=k++;
				if(id[a*2+2]==-1)id[a*2+2]=k++;
			}
		}
		for(int i=0;i<k;i++)seg[i].ini(n);
	}
	void up(int a,node &q){
		a+=(1<<13)-1;
		seg[id[a]]=q;
		while(a>0){
			a=(a-1)/2;
			seg[id[a]]=seg[id[a*2+1]].plus(seg[id[a*2+2]]);
		}
	}
	int dis(int a,int b){
		return seg[id[0]].d[a][b];
	}
};
int h[5000][100],w[5000][100],n,m,p[100];
SEG s;
void change(int x){
	p[0]=0;
	for(int i=1;i<m;i++)p[i]=p[i-1]+h[x][i-1];
	node res;
	res.ini(m);
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			res.d[i][j]=p[max(i,j)]-p[min(i,j)]+w[x][j];
		}
	}
	s.up(x,res);
}
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.dis(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 329 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 34 ms 41720 KB Output is correct
2 Correct 33 ms 41796 KB Output is correct
3 Correct 33 ms 41788 KB Output is correct
4 Correct 95 ms 117764 KB Output is correct
5 Correct 95 ms 117880 KB Output is correct
6 Correct 95 ms 117752 KB Output is correct
7 Correct 94 ms 117676 KB Output is correct
8 Correct 91 ms 113784 KB Output is correct
9 Correct 94 ms 117752 KB Output is correct
10 Correct 91 ms 113788 KB Output is correct
11 Correct 173 ms 118748 KB Output is correct
12 Correct 94 ms 117752 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 336 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 Runtime error 254 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

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