oj.uz

Submission #126078

# Submission time Handle Problem Language Result Execution time Memory
126078 2019-07-07T02:20:22 Z nxteru Wombats (IOI13_wombats) C++14
12 / 100
 314 ms 262148 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
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[10000];
	void ini(int x){
		n=x;
		for(int i=0;i<10000;i++)seg[i].ini(n);
	}
	void up(int a,node &q){
		a+=(5000)-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];
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.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 314 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 36 ms 45560 KB Output is correct
2 Correct 36 ms 45560 KB Output is correct
3 Correct 36 ms 45560 KB Output is correct
4 Correct 157 ms 199316 KB Output is correct
5 Correct 158 ms 199288 KB Output is correct
6 Correct 185 ms 199464 KB Output is correct
7 Correct 158 ms 199260 KB Output is correct
8 Correct 154 ms 191436 KB Output is correct
9 Correct 157 ms 199416 KB Output is correct
10 Correct 151 ms 191460 KB Output is correct
11 Correct 252 ms 200440 KB Output is correct
12 Correct 158 ms 199484 KB Output is correct

Subtask #3
0 / 16.0

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