oj.uz

Submission #1067956

# Submission time Handle Problem Language Result Execution time Memory
1067956 2024-08-21T06:06:45 Z sleepntsheep Wombats (IOI13_wombats) C++17
27 / 100
 38 ms 13148 KB 
#pragma GCC optimize("O3,unroll-loops")
#include "wombats.h"
#include <cstdio>
#include <cstdlib>
#include <set>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;

#ifndef ROW
#define ROW 5000
#endif

int r, c, h[ROW][100], v[ROW + 1][100];

struct node {
	int a[2][2] {};
	node() {}
	node(int row) {
		static int ph[100];
		ph[0] = 0;
		for (int j = 0; j + 1 < c; ++j)
			ph[j + 1] = ph[j] + h[row][j];

		for (int i = 0; i < c; ++i) {
			for (int j = 0; j < c; ++j)
				if (j < i)
					a[i][j] = v[row][j] + ph[i] - ph[j];
				else
					a[i][j] = v[row][j] + ph[j] - ph[i];
		}
	}
	
	node (node up, node down) {
		for (int i = 0; i < c; ++i) for (int j = 0; j < c; ++j) {
			a[i][j] = 1e9;
			for (int k = 0; k < c; ++k)
				a[i][j] = min(a[i][j], up.a[i][k] + down.a[k][j]);
		}
	}
};

node st[20001];

void build(int v, int l, int r) {
	if (l == r) {
		st[v] = node(l);
		return;
	}
	int m  = (l + r) / 2;
	build(2 * v + 1, l, m);
	build(2 * v + 2, m + 1, r);
	st[v] = node(st[v * 2 + 1], st[v * 2 + 2]);
}

void upd(int v, int l, int r, int k) {
	if (l == r) {
		st[v] = node(l);
		return;
	}
	int m  = (l + r) / 2;
	if (k <= m) upd(2 * v + 1, l, m, k);
	else upd(2 * v + 2, m + 1, r, k);
	st[v] = node(st[v * 2 + 1], st[v * 2 + 2]);
}

void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	upd(0, 0, r - 1, P);
}

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

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

int escape(int V1, int V2) {
	auto &x = st[0];
	return x.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]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 38 ms 11344 KB Output is correct
4 Correct 2 ms 9560 KB Output is correct
5 Correct 2 ms 9564 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Runtime error 6 ms 12892 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 12960 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 5 ms 12376 KB Output is correct
4 Correct 22 ms 13020 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 13148 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 13072 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -