답안 #16105 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16105	2015-08-16T04:20:26 Z	gs14004	웜뱃 (IOI13_wombats)	C++14	100 / 100	7343 ms	191616 KB

wombats

#include "wombats.h"
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

struct node{
	int adj[205][205];
};

int a[5000][200], b[5000][200];
int n, m;
int opt[205][205];

node merge(node& a, node& b){
	node c;
	memset(c.adj,0x3f,sizeof(c.adj));
	// opt(i-1, j) <= opt(i,j) <= opt(i,j+1)
	for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			if(c.adj[0][i] > a.adj[0][j] + b.adj[j][i]){
				c.adj[0][i] = a.adj[0][j] + b.adj[j][i];
				opt[0][i] = j;
			}
		}
	}
	for(int i=1; i<m; i++){
		opt[i][m] = m-1;
		for(int j=m-1; j>=0; j--){
			for(int k=opt[i-1][j]; k<=opt[i][j+1]; k++){
				if(c.adj[i][j] > a.adj[i][k] + b.adj[k][j]){
					c.adj[i][j] = a.adj[i][k] + b.adj[k][j];
					opt[i][j] = k;
				}
			}
		}
	}
	return c;
}

node tmp[11];
struct seg{
	node tree[1050];
	void remake(int s, int e, int p){
		for(int i=s; i<=e; i++){
			for(int j=0; j<m; j++){
				for(int k=0; k<m; k++){
					tmp[i-s].adj[j][k] = b[i][k] + abs((j ? a[i][j-1] : 0) - (k ? a[i][k-1] : 0));
				}
			}
		}
		tree[p] = tmp[0];
		for(int i=1; i<=e-s; i++){
			tree[p] = merge(tree[p], tmp[i]);
		}
	}
	void add(int pos, int ps, int pe, int p){
		if(pe - ps <= 10){
			remake(ps, pe, p);
			return;
		}
		int pm = (ps + pe) / 2;
		if(pos <= pm) add(pos, ps, pm, 2*p);
		else add(pos, pm+1, pe, 2*p+1);
		tree[p] = merge(tree[2*p], tree[2*p+1]);
	}
	void init(int ps, int pe, int p){
		if(pe - ps <= 10){
			remake(ps, pe, p);
			return;
		}
		int pm = (ps + pe) / 2;
		init(ps, pm, 2*p);
		init(pm+1, pe, 2*p+1);
		tree[p] = merge(tree[2*p], tree[2*p+1]);
	}
}seg;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	n = R, m = C;
	for(int i=0; i<R; i++){
		for(int j=0; j<C; j++){
			a[i][j] = H[i][j] + (j ? a[i][j-1] : 0);
			b[i][j] = V[i][j];
		}
	}
	seg.init(0,n-1,1);
}

void changeH(int P, int Q, int W) {
    int diff = W - (a[P][Q] - (Q ? a[P][Q-1] : 0));
    for(int i=Q; i<m; i++){
    	a[P][i] += diff;
	}
    seg.add(P,0,n-1,1); 
}

void changeV(int P, int Q, int W) {
	b[P][Q] = W;
	seg.add(P,0,n-1,1);
}

int escape(int V1, int V2) {
	return seg.tree[1].adj[V1][V2];
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	402 ms	191444 KB	Output is correct - 505 tokens
2	Correct	419 ms	191448 KB	Output is correct - 505 tokens
3	Correct	483 ms	191452 KB	Output is correct - 200005 tokens
4	Correct	397 ms	191452 KB	Output is correct - 505 tokens
5	Correct	374 ms	191444 KB	Output is correct - 505 tokens
6	Correct	0 ms	191120 KB	Output is correct - 6 tokens
7	Correct	0 ms	191116 KB	Output is correct - 6 tokens
8	Correct	0 ms	191116 KB	Output is correct - 6 tokens

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	191116 KB	Output is correct - 6 tokens
2	Correct	0 ms	191124 KB	Output is correct - 6 tokens
3	Correct	0 ms	191116 KB	Output is correct - 6 tokens
4	Correct	0 ms	191120 KB	Output is correct - 405 tokens
5	Correct	0 ms	191116 KB	Output is correct - 405 tokens
6	Correct	0 ms	191124 KB	Output is correct - 405 tokens
7	Correct	0 ms	191120 KB	Output is correct - 405 tokens
8	Correct	0 ms	191116 KB	Output is correct - 366 tokens
9	Correct	0 ms	191120 KB	Output is correct - 405 tokens
10	Correct	3 ms	191120 KB	Output is correct - 366 tokens
11	Correct	88 ms	191116 KB	Output is correct - 200005 tokens
12	Correct	0 ms	191120 KB	Output is correct - 405 tokens

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	166 ms	191284 KB	Output is correct - 105 tokens
2	Correct	137 ms	191280 KB	Output is correct - 105 tokens
3	Correct	173 ms	191288 KB	Output is correct - 105 tokens
4	Correct	167 ms	191284 KB	Output is correct - 105 tokens
5	Correct	177 ms	191284 KB	Output is correct - 105 tokens
6	Correct	0 ms	191120 KB	Output is correct - 6 tokens
7	Correct	0 ms	191120 KB	Output is correct - 6 tokens
8	Correct	0 ms	191116 KB	Output is correct - 6 tokens
9	Correct	594 ms	191280 KB	Output is correct - 105 tokens
10	Correct	0 ms	191120 KB	Output is correct - 8 tokens

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	397 ms	191452 KB	Output is correct - 1005 tokens
2	Correct	378 ms	191448 KB	Output is correct - 1005 tokens
3	Correct	404 ms	191616 KB	Output is correct - 1005 tokens
4	Correct	446 ms	191444 KB	Output is correct - 100005 tokens

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	160 ms	191284 KB	Output is correct - 105 tokens
2	Correct	139 ms	191284 KB	Output is correct - 105 tokens
3	Correct	167 ms	191284 KB	Output is correct - 105 tokens
4	Correct	170 ms	191280 KB	Output is correct - 105 tokens
5	Correct	164 ms	191280 KB	Output is correct - 105 tokens
6	Correct	393 ms	191452 KB	Output is correct - 1005 tokens
7	Correct	389 ms	191452 KB	Output is correct - 1005 tokens
8	Correct	421 ms	191616 KB	Output is correct - 1005 tokens
9	Correct	440 ms	191448 KB	Output is correct - 100005 tokens
10	Correct	395 ms	191444 KB	Output is correct - 505 tokens
11	Correct	376 ms	191444 KB	Output is correct - 505 tokens
12	Correct	484 ms	191452 KB	Output is correct - 200005 tokens
13	Correct	389 ms	191448 KB	Output is correct - 505 tokens
14	Correct	389 ms	191448 KB	Output is correct - 505 tokens
15	Correct	0 ms	191124 KB	Output is correct - 6 tokens
16	Correct	0 ms	191120 KB	Output is correct - 6 tokens
17	Correct	0 ms	191116 KB	Output is correct - 6 tokens
18	Correct	3 ms	191120 KB	Output is correct - 405 tokens
19	Correct	0 ms	191120 KB	Output is correct - 405 tokens
20	Correct	0 ms	191116 KB	Output is correct - 405 tokens
21	Correct	0 ms	191124 KB	Output is correct - 405 tokens
22	Correct	0 ms	191120 KB	Output is correct - 366 tokens
23	Correct	0 ms	191120 KB	Output is correct - 405 tokens
24	Correct	0 ms	191120 KB	Output is correct - 366 tokens
25	Correct	93 ms	191120 KB	Output is correct - 200005 tokens
26	Correct	0 ms	191116 KB	Output is correct - 405 tokens
27	Correct	590 ms	191280 KB	Output is correct - 105 tokens
28	Correct	1911 ms	191452 KB	Output is correct - 50005 tokens
29	Correct	2056 ms	191444 KB	Output is correct - 50005 tokens
30	Correct	2061 ms	191444 KB	Output is correct - 50005 tokens
31	Correct	2040 ms	191448 KB	Output is correct - 200005 tokens
32	Correct	0 ms	191120 KB	Output is correct - 8 tokens

Subtask #6
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	163 ms	191284 KB	Output is correct - 105 tokens
2	Correct	133 ms	191284 KB	Output is correct - 105 tokens
3	Correct	168 ms	191288 KB	Output is correct - 105 tokens
4	Correct	174 ms	191284 KB	Output is correct - 105 tokens
5	Correct	160 ms	191284 KB	Output is correct - 105 tokens
6	Correct	366 ms	191444 KB	Output is correct - 1005 tokens
7	Correct	396 ms	191448 KB	Output is correct - 1005 tokens
8	Correct	407 ms	191608 KB	Output is correct - 1005 tokens
9	Correct	440 ms	191448 KB	Output is correct - 100005 tokens
10	Correct	383 ms	191448 KB	Output is correct - 505 tokens
11	Correct	381 ms	191452 KB	Output is correct - 505 tokens
12	Correct	461 ms	191448 KB	Output is correct - 200005 tokens
13	Correct	389 ms	191448 KB	Output is correct - 505 tokens
14	Correct	374 ms	191444 KB	Output is correct - 505 tokens
15	Correct	2950 ms	191452 KB	Output is correct - 11 tokens
16	Correct	7343 ms	191616 KB	Output is correct - 200005 tokens
17	Correct	0 ms	191120 KB	Output is correct - 6 tokens
18	Correct	0 ms	191120 KB	Output is correct - 6 tokens
19	Correct	0 ms	191124 KB	Output is correct - 6 tokens
20	Correct	3 ms	191120 KB	Output is correct - 405 tokens
21	Correct	0 ms	191120 KB	Output is correct - 405 tokens
22	Correct	0 ms	191116 KB	Output is correct - 405 tokens
23	Correct	0 ms	191120 KB	Output is correct - 405 tokens
24	Correct	0 ms	191116 KB	Output is correct - 366 tokens
25	Correct	0 ms	191120 KB	Output is correct - 405 tokens
26	Correct	0 ms	191116 KB	Output is correct - 366 tokens
27	Correct	90 ms	191116 KB	Output is correct - 200005 tokens
28	Correct	0 ms	191116 KB	Output is correct - 405 tokens
29	Correct	602 ms	191280 KB	Output is correct - 105 tokens
30	Correct	1942 ms	191448 KB	Output is correct - 50005 tokens
31	Correct	5980 ms	191448 KB	Output is correct - 100005 tokens
32	Correct	6016 ms	191452 KB	Output is correct - 100005 tokens
33	Correct	2031 ms	191448 KB	Output is correct - 50005 tokens
34	Correct	6386 ms	191448 KB	Output is correct - 100005 tokens
35	Correct	2038 ms	191444 KB	Output is correct - 50005 tokens
36	Correct	6503 ms	191448 KB	Output is correct - 100005 tokens
37	Correct	2015 ms	191448 KB	Output is correct - 200005 tokens
38	Correct	6433 ms	191612 KB	Output is correct - 200005 tokens
39	Correct	0 ms	191120 KB	Output is correct - 8 tokens
40	Correct	6692 ms	191452 KB	Output is correct - 100005 tokens

답안 #16105

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 21.0 / 21.0

Subtask #6 24.0 / 24.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
21.0 / 21.0

Subtask #6
24.0 / 24.0