답안 #31453 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31453	2017-08-27T11:01:53 Z	jun6873	웜뱃 (IOI13_wombats)	C++11	100 / 100	10939 ms	251520 KB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

struct matrix {
	int a[202][202];
};

const int lim = 1400;
int r, c, h[5004][204], v[5004][204], hs[5004][204], thr[204][204];
bool f[lim];
matrix m[lim], all;

void printmat(matrix k){
	for (int i=0; i<=c; i++) {
		for (int j=0; j<=c; j++) printf("%d ", k.a[i][j]);
		puts("");
	}
	puts("");
}

inline int hsum(int k, int x, int y) {
	if (x>y) swap(x, y);
	return x ? (hs[k][y] - hs[k][x]) : hs[k][y];
}

matrix sum(matrix &a, matrix &b, int k) {
	matrix ret;
	for (int i=0; i<=c; i++) thr[i][c-i+1] = c-1;
	for (int tog=0; tog<2; tog++) for (int j=c-1; j>=0; j--) for (int i=0; i+j<c; i++) {
		int mn = 2e9, mp = -1;
		int x = tog ? (i+j) : i, y = tog ? i : (i+j);
		for (int t=thr[j+1][i]; t<=thr[j+1][i+1]; t++) {
			int now = a.a[x][t] + v[k][t] + b.a[t][y];
			if (now <= mn) mn = now, mp = t;
		}
		if (tog) ret.a[i+j][i] = mn;
		else ret.a[i][i+j] = mn;
		thr[j][i+1] = mp;
	}
	return ret;
}

matrix base(int k) {
	matrix ret;
	for (int i=0; i<c; i++) for (int j=0; j<c; j++) ret.a[i][j] = hsum(k, i, j);
	return ret;
}

matrix get(int s, int e, int x, int all) {
	if (s==e) return base(s);
	if (!all and x<lim and f[x]) return m[x];
	int mid = (s+e)/2;
	if (x<lim) f[x] = 1;
	matrix l = get(s, mid, 2*x, all), r = get(mid+1, e, 2*x+1, all);
	matrix ret = sum(l, r, mid);
	if (x<lim) m[x] = ret;
	return ret;
}

matrix update(int s, int e, int x, int p) {
	if (s==e) return base(s);
	int k = (s+e)/2;
	if (p<=k) update(s, k, 2*x, p);
	else update(k+1, e, 2*x+1, p);
	if (x<lim) f[x] = 0;
	return get(s, e, x, 0);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R; c = C;
    for (int i=0; i<r; i++) for (int j=0; j<c-1; j++) h[i][j] = H[i][j], hs[i][j+1] = hs[i][j] + h[i][j];
    for (int i=0; i<r-1; i++) for (int j=0; j<c; j++) v[i][j] = V[i][j];
    all = get(0, r-1, 1, 1);
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    for (int j=0; j<c-1; j++) hs[P][j+1] = hs[P][j] + h[P][j];
    all = update(0, r-1, 1, P);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    all = update(0, r-1, 1, P);
}

int escape(int V1, int V2) {
    return all.a[V1][V2];
}

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
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	539 ms	251516 KB	Output is correct
2	Correct	609 ms	251512 KB	Output is correct
3	Correct	729 ms	251516 KB	Output is correct
4	Correct	736 ms	251516 KB	Output is correct
5	Correct	666 ms	251512 KB	Output is correct
6	Correct	0 ms	245776 KB	Output is correct
7	Correct	0 ms	245776 KB	Output is correct
8	Correct	0 ms	245776 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	245780 KB	Output is correct
2	Correct	0 ms	245776 KB	Output is correct
3	Correct	0 ms	245772 KB	Output is correct
4	Correct	0 ms	247692 KB	Output is correct
5	Correct	3 ms	247688 KB	Output is correct
6	Correct	3 ms	247692 KB	Output is correct
7	Correct	0 ms	247688 KB	Output is correct
8	Correct	3 ms	247684 KB	Output is correct
9	Correct	3 ms	247688 KB	Output is correct
10	Correct	0 ms	247688 KB	Output is correct
11	Correct	96 ms	247688 KB	Output is correct
12	Correct	3 ms	247692 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	203 ms	248644 KB	Output is correct
2	Correct	149 ms	248648 KB	Output is correct
3	Correct	199 ms	248648 KB	Output is correct
4	Correct	229 ms	248644 KB	Output is correct
5	Correct	199 ms	248648 KB	Output is correct
6	Correct	0 ms	245780 KB	Output is correct
7	Correct	0 ms	245776 KB	Output is correct
8	Correct	0 ms	245776 KB	Output is correct
9	Correct	706 ms	248648 KB	Output is correct
10	Correct	0 ms	246416 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	603 ms	251512 KB	Output is correct
2	Correct	526 ms	251520 KB	Output is correct
3	Correct	619 ms	251520 KB	Output is correct
4	Correct	739 ms	251516 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	179 ms	248648 KB	Output is correct
2	Correct	143 ms	248644 KB	Output is correct
3	Correct	203 ms	248648 KB	Output is correct
4	Correct	209 ms	248644 KB	Output is correct
5	Correct	189 ms	248644 KB	Output is correct
6	Correct	613 ms	251512 KB	Output is correct
7	Correct	623 ms	251520 KB	Output is correct
8	Correct	693 ms	251516 KB	Output is correct
9	Correct	613 ms	251520 KB	Output is correct
10	Correct	566 ms	251516 KB	Output is correct
11	Correct	596 ms	251516 KB	Output is correct
12	Correct	676 ms	251516 KB	Output is correct
13	Correct	696 ms	251512 KB	Output is correct
14	Correct	653 ms	251520 KB	Output is correct
15	Correct	0 ms	245780 KB	Output is correct
16	Correct	0 ms	245776 KB	Output is correct
17	Correct	0 ms	245776 KB	Output is correct
18	Correct	3 ms	247688 KB	Output is correct
19	Correct	3 ms	247688 KB	Output is correct
20	Correct	0 ms	247688 KB	Output is correct
21	Correct	3 ms	247688 KB	Output is correct
22	Correct	0 ms	247692 KB	Output is correct
23	Correct	3 ms	247692 KB	Output is correct
24	Correct	0 ms	247688 KB	Output is correct
25	Correct	103 ms	247692 KB	Output is correct
26	Correct	0 ms	247684 KB	Output is correct
27	Correct	806 ms	248648 KB	Output is correct
28	Correct	3219 ms	251520 KB	Output is correct
29	Correct	2533 ms	251036 KB	Output is correct
30	Correct	3189 ms	251516 KB	Output is correct
31	Correct	2623 ms	251516 KB	Output is correct
32	Correct	0 ms	246416 KB	Output is correct

Subtask #6
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	176 ms	248652 KB	Output is correct
2	Correct	149 ms	248648 KB	Output is correct
3	Correct	176 ms	248648 KB	Output is correct
4	Correct	169 ms	248644 KB	Output is correct
5	Correct	173 ms	248644 KB	Output is correct
6	Correct	633 ms	251516 KB	Output is correct
7	Correct	616 ms	251516 KB	Output is correct
8	Correct	666 ms	251512 KB	Output is correct
9	Correct	716 ms	251512 KB	Output is correct
10	Correct	649 ms	251512 KB	Output is correct
11	Correct	619 ms	251516 KB	Output is correct
12	Correct	726 ms	251520 KB	Output is correct
13	Correct	726 ms	251512 KB	Output is correct
14	Correct	653 ms	251516 KB	Output is correct
15	Correct	3609 ms	251516 KB	Output is correct
16	Correct	9526 ms	251516 KB	Output is correct
17	Correct	0 ms	245776 KB	Output is correct
18	Correct	0 ms	245776 KB	Output is correct
19	Correct	0 ms	245772 KB	Output is correct
20	Correct	0 ms	247688 KB	Output is correct
21	Correct	0 ms	247688 KB	Output is correct
22	Correct	0 ms	247692 KB	Output is correct
23	Correct	0 ms	247692 KB	Output is correct
24	Correct	0 ms	247692 KB	Output is correct
25	Correct	0 ms	247684 KB	Output is correct
26	Correct	0 ms	247692 KB	Output is correct
27	Correct	116 ms	247688 KB	Output is correct
28	Correct	0 ms	247692 KB	Output is correct
29	Correct	706 ms	248644 KB	Output is correct
30	Correct	2799 ms	251512 KB	Output is correct
31	Correct	10939 ms	251520 KB	Output is correct
32	Correct	8269 ms	251516 KB	Output is correct
33	Correct	2533 ms	251040 KB	Output is correct
34	Correct	7509 ms	251040 KB	Output is correct
35	Correct	2786 ms	251520 KB	Output is correct
36	Correct	9783 ms	251520 KB	Output is correct
37	Correct	2323 ms	251520 KB	Output is correct
38	Correct	8743 ms	251512 KB	Output is correct
39	Correct	0 ms	246416 KB	Output is correct
40	Correct	8389 ms	251036 KB	Output is correct

답안 #31453

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