oj.uz

Submission #97019

# Submission time Handle Problem Language Result Execution time Memory
97019 2019-02-13T10:47:58 Z E869120 Wombats (IOI13_wombats) C++14
76 / 100
 11759 ms 255136 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

int H, W, size_, A1[10009][209], A2[10009][209], dat[5509][109][109], U[16384]; bool ok[16384];
int M[2][109][109];

void getval(int ty, int pos) {
	pos += size_;
	for (int i = 0; i < W; i++) {
		M[ty][i][i] = A2[pos - size_][i]; int s = 0;
		for (int j = i + 1; j < W; j++) {
			s += A1[pos - size_][j - 1];
			M[ty][i][j] = s + A2[pos - size_][j];
		}
		s = 0;
		for (int j = i - 1; j >= 0; j--) {
			s += A1[pos - size_][j];
			M[ty][i][j] = s + A2[pos - size_][j];
		}
	}
}

void update(int pos) {
	if (ok[pos * 2 + 1] == false) {
		if (pos * 2 < size_) {
			for (int i = 0; i < W; i++) {
				for (int j = 0; j < W; j++) dat[U[pos]][i][j] = dat[U[pos * 2]][i][j];
			}
		}
		else {
			getval(0, pos * 2 - size_);
			for (int i = 0; i < W; i++) {
				for (int j = 0; j < W; j++) dat[U[pos]][i][j] = M[0][i][j];
			}
		}
		return;
	}
	int L = pos * 2, R = pos * 2 + 1;
	
	if (L < size_) {
		for (int i = 0; i < W; i++) {
			for (int j = 0; j < W; j++) {
				M[0][i][j] = dat[U[L]][i][j];
				M[1][i][j] = dat[U[R]][i][j];
			}
		}
	}
	else {
		getval(0, L - size_);
		getval(1, R - size_);
	}
	
	int rev = U[pos];
	for (int i = 0; i < W; i++) { for (int j = 0; j < W; j++) dat[rev][i][j] = (1 << 30); }
	for (int i = 0; i < W; i++) {
		for (int j = 0; j < W; j++) {
			for (int k = 0; k < W; k++) dat[rev][i][k] = min(dat[rev][i][k], M[0][i][j] + M[1][j][k]);
		}
	}
}

void recharge(int pos, int B){
	pos += size_;
	
	while (pos >= 2) {
		if (B == 2 && pos % 2 == 0) break;
		pos /= 2;
		update(pos);
	}
}

void init(int R, int C, int I[5000][200], int V[5000][200]) {
	size_ = 1; while (size_ < R) size_ *= 2;
	H = R; W = C;
	for (int i = 0; i < H; i++) {
		int cx = i + size_; ok[cx] = true;
		while (cx >= 2) { cx /= 2; ok[cx] = true; }
	}
	int cntv = 0;
	for (int i = 0; i < size_; i++) {
		if (ok[i] == true) { U[i] = cntv; cntv++; }
	}
    for (int i = 0; i < H; i++) {
		for(int j = 0; j < W - 1; j++) A1[i][j] = I[i][j];
	}
	for (int i = 0; i < H - 1; i++) {
		for (int j = 0; j < W; j++) A2[i][j] = V[i][j];
	}
	for (int i = 0; i < size_; i++) recharge(i, 2);
	
	/*for (int i = 0; i < cntv; i++) {
		cout<<i<<":"<<endl;
		for (int j = 0; j < W; j++) {
			for (int k = 0; k < W; k++) cout<<dat[i][j][k]<<" "; cout<<endl;
		}
		cout<<endl;
	}*/
}

void changeH(int P, int Q, int T) {
    A1[P][Q] = T;
    recharge(P, 1);
}

void changeV(int P, int Q, int T) {
    A2[P][Q] = T;
    recharge(P, 1);
}

int escape(int V1, int V2) {
	return dat[U[1]][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

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28920 KB Output is correct
2 Correct 29 ms 28928 KB Output is correct
3 Correct 127 ms 30372 KB Output is correct
4 Correct 26 ms 28800 KB Output is correct
5 Correct 24 ms 28928 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 428 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 73 ms 1784 KB Output is correct
12 Correct 3 ms 768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 5676 KB Output is correct
2 Correct 739 ms 5496 KB Output is correct
3 Correct 817 ms 5496 KB Output is correct
4 Correct 734 ms 5560 KB Output is correct
5 Correct 744 ms 5576 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 404 KB Output is correct
8 Correct 2 ms 356 KB Output is correct
9 Correct 3398 ms 5644 KB Output is correct
10 Correct 2 ms 368 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 39040 KB Output is correct
2 Correct 30 ms 39160 KB Output is correct
3 Correct 33 ms 39060 KB Output is correct
4 Correct 61 ms 39768 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 5596 KB Output is correct
2 Correct 801 ms 5624 KB Output is correct
3 Correct 827 ms 5552 KB Output is correct
4 Correct 700 ms 5496 KB Output is correct
5 Correct 716 ms 5520 KB Output is correct
6 Correct 32 ms 39040 KB Output is correct
7 Correct 31 ms 39040 KB Output is correct
8 Correct 32 ms 39040 KB Output is correct
9 Correct 65 ms 39800 KB Output is correct
10 Correct 26 ms 28928 KB Output is correct
11 Correct 28 ms 28928 KB Output is correct
12 Correct 95 ms 30456 KB Output is correct
13 Correct 25 ms 28800 KB Output is correct
14 Correct 28 ms 28792 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 3 ms 768 KB Output is correct
19 Correct 4 ms 640 KB Output is correct
20 Correct 3 ms 640 KB Output is correct
21 Correct 3 ms 640 KB Output is correct
22 Correct 3 ms 636 KB Output is correct
23 Correct 4 ms 640 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 82 ms 1656 KB Output is correct
26 Correct 3 ms 640 KB Output is correct
27 Correct 3581 ms 5752 KB Output is correct
28 Correct 11369 ms 249924 KB Output is correct
29 Correct 10208 ms 208172 KB Output is correct
30 Correct 11076 ms 208696 KB Output is correct
31 Correct 11759 ms 255136 KB Output is correct
32 Correct 3 ms 384 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 5624 KB Output is correct
2 Correct 826 ms 5556 KB Output is correct
3 Correct 824 ms 5828 KB Output is correct
4 Correct 780 ms 5656 KB Output is correct
5 Correct 778 ms 5496 KB Output is correct
6 Correct 38 ms 39160 KB Output is correct
7 Correct 34 ms 39032 KB Output is correct
8 Correct 47 ms 39032 KB Output is correct
9 Correct 84 ms 40020 KB Output is correct
10 Correct 33 ms 28920 KB Output is correct
11 Correct 27 ms 28920 KB Output is correct
12 Correct 95 ms 30712 KB Output is correct
13 Correct 28 ms 28928 KB Output is correct
14 Correct 29 ms 28928 KB Output is correct
15 Runtime error 247 ms 33204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -