oj.uz

답안 #126139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126139 2019-07-07T05:51:04 Z nxteru 웜뱃 (IOI13_wombats) C++14
0 / 100
 831 ms 176360 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--){
			int *b=a[i+n+1],*c=a[i+n];
			for(int j=max(-i,0);i+j<n&&j<n;j++){
				s=INF;
				int x,y,z=i+j;
				if(j-1>=0)x=b[j-1];
				else x=0;
				if(z+1<n)y=b[j];
				else y=n-1;
				for(int k=x;k<=y;k++){
					if(d[z][k]+q.d[k][j]<s){
						x=k;
						s=d[z][k]+q.d[k][j];
					}
				}
				c[j]=x;
				res.d[z][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[205][205];
SEG s;
node res[B];
void change(int x){
	x=x/B;
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(i==j)p[i][j]=0;
			else p[i][j]=INF;
		}
	}
	for(int i=0;i<B&&x*B+i<n;i++){
		for(int j=1;j<m;j++){
			p[i][j]=min(p[i][j],p[i][j-1]+h[x*B+i][j-1]);
		}
		for(int j=m-2;j>=0;j--){
			p[i][j]=min(p[i][j],p[i][j+1]+h[x*B+i][j]);
		}
		for(int j=0;j<m;j++)p[i][j]+=h[x*B+i][j];
	}
	node res;
	for(int i=0;i<m;i++)for(int j=0;j<m;j++)res.d[i][j]=p[i][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.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

# 결과 실행 시간 메모리 Grader output
1 Correct 816 ms 165128 KB Output is correct
2 Incorrect 831 ms 165240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 6268 KB Output is correct
2 Incorrect 7 ms 6264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 228 ms 176212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 819 ms 173024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 226 ms 176248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 229 ms 176360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -