oj.uz

Submission #1067791

# Submission time Handle Problem Language Result Execution time Memory
1067791 2024-08-21T03:20:55 Z sleepntsheep Wombats (IOI13_wombats) C++17
39 / 100
 2835 ms 17340 KB 
#include "wombats.h"
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

template <typename T>
using ve = vector<T>;


int r, c, at[9999], h[5000][200], v[5000][200];
int sum = 0;


int c_is_2_dp(int V1, int V2) {
	static int dp[5001][2];
	dp[0][V1] = 0;
	dp[0][!V1] = h[0][0];

	for (int i = 1; i < r; ++i) {
		dp[i][0] = dp[i - 1][0] + v[i - 1][0];
		dp[i][1] = dp[i - 1][1] + v[i - 1][1];
		dp[i][0] = min(dp[i][0], dp[i][1] + h[i][0]);
		dp[i][1] = min(dp[i][1], dp[i][0] + h[i][0]);
	}
	return dp[r - 1][V2];
}

void changeH(int P, int Q, int W) {
	if (c == 2) {
		h[P][Q] = W;
	}
	/* ... */
}

void changeV(int P, int Q, int W) {
	if (c == 1) {
		sum += W - at[P];
		at[P] = W;
	} else if (c == 2) {
		v[P][Q] = W;
	}
	/* ... */
}

static int floyd[401][401];
void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R, c = C;

	if (c == 1)
		for (int i = 0; i < r; ++i) changeV(i, 0, V[i][0]);
	else if (c == 2) {
		for (int i = 0; i < r; ++i) {
			if (i + 1 < r)
				changeV(i, 0, V[i][0]), changeV(i, 1, V[i][1]);
			changeH(i, 0, H[i][0]);
		}
	} else if (r <= 20 and c <= 20) {
		auto id = [&](int p, int q) { return p * c + q; };
		memset(floyd, 63, sizeof floyd);
		for (int i = 0; i < r * c; ++i) floyd[i][i] = 0;
		for (int i = 0; i + 1 < r; ++i) for (int j = 0; j < c; ++j) {
			int u = id(i, j), v = id(i + 1, j);
			floyd[u][v] = min(floyd[u][v], V[i][j]);
		}
		for (int i = 0 ; i < r; ++i) for (int j = 0; j + 1 < c; ++j) {
			int u = id(i, j), v = id(i, j + 1);
			floyd[u][v] = min(floyd[u][v], H[i][j]);
			floyd[v][u] = min(floyd[v][u], H[i][j]);
		}
		for (int bruh=3;bruh--;)for(int i=0;i<r*c;++i)for(int j=0;j<r*c;++j)for(int k=0;k<r*c;++k)
			floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j]);
	}
}

int escape(int V1, int V2) {
	if (c == 1)
		return sum;
	else if (c == 2)
		return c_is_2_dp(V1, V2);
	return floyd[V1][c * (r - 1) + 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 4184 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 36 ms 5940 KB Output is correct
4 Correct 2 ms 4184 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 167 ms 1068 KB Output is correct
5 Correct 167 ms 856 KB Output is correct
6 Correct 166 ms 860 KB Output is correct
7 Correct 169 ms 1112 KB Output is correct
8 Correct 124 ms 860 KB Output is correct
9 Correct 144 ms 856 KB Output is correct
10 Correct 149 ms 1068 KB Output is correct
11 Correct 215 ms 1836 KB Output is correct
12 Correct 183 ms 856 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15964 KB Output is correct
2 Correct 35 ms 15964 KB Output is correct
3 Correct 35 ms 15960 KB Output is correct
4 Correct 2835 ms 17340 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -