oj.uz

Submission #765121

# Submission time Handle Problem Language Result Execution time Memory
765121 2023-06-24T08:28:56 Z Sohsoh84 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 5000 + 10;
const ll MAXM = 100 + 10;

int n, m, H[MAXN][MAXM], V[MAXN][MAXM], ps[MAXN][MAXM], sg[MAXN << 1][MAXM][MAXM], opt[MAXM][MAXM], lc[MAXN << 1], rc[MAXN << 1], sgsz = 1;

inline void update_ps(int i) {
	for (int j = 2; j <= m; j++)
		ps[i][j] = ps[i][j - 1] + H[i][j - 1];
}

inline void update_ans(int mid, int v) {
	for (int x = 1; x <= m; x++) {
		for (int y = 1; y <= m; y++) {
			sg[v][x][y] = sg[lc[v]][x][x] + V[mid][x] + sg[rc[v]][x][y];
			for (int f = 1; f <= m; f++) {
				sg[v][x][y] = min(sg[v][x][y], sg[lc[v]][x][f] + V[mid][f] + sg[rc[v]][f][y]);
			}
		}
	}
}

void build(int l = 1, int r = n, int v = 1) {
	if (l == r) {
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= m; j++)
				sg[v][i][j] = ps[l][max(i, j)] - ps[l][min(i, j)];
	} else {
		int mid = (l + r) >> 1;
		lc[v] = ++sgsz;
		rc[v] = ++sgsz;
		build(l, mid, lc[v]);
		build(mid + 1, r, rc[v]);
		update_ans(mid, v);
	}
}

void update(int ind, int l = 1, int r = n, int v = 1) {
	if (l == r) {
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= m; j++)
				sg[v][i][j] = ps[l][max(i, j)] - ps[l][min(i, j)];	
	} else {
		int mid = (l + r) >> 1;
		if (ind <= mid) update(ind, l, mid, lc[v]);
		else update(ind, mid + 1, r, rc[v]);
		
		update_ans(mid, v);
	}
}

void init(int R_, int C_, int H_[5000][200], int V_[5000][200]) {
	n = R_, m = C_;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < m; j++)
			H[i][j] = H_[i - 1][j - 1];
	
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= m; j++)
			V[i][j] = V_[i - 1][j - 1];

	for (int i = 1; i <= n; i++)
		update_ps(i);
	
	build();
}

void changeH(int P, int Q, int W) {
	P++, Q++;
	H[P][Q] = W;
	update_ps(P);
	update(P);
}

void changeV(int P, int Q, int W) {
	P++, Q++;
	V[P][Q] = W;
	update(P);
}

int escape(int V1, int V2) {
	V1++, V2++;
	return sg[1][V1][V2];
}

// TODO: 1-base
// TODO: check fit in ll
// TODO: change max limits
// TODO: check n == 1
// TODO: check bounds(n / m)

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 18 ms 47316 KB Output is correct
2 Correct 17 ms 47360 KB Output is correct
3 Correct 68 ms 48976 KB Output is correct
4 Correct 19 ms 47316 KB Output is correct
5 Correct 18 ms 47388 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 55 ms 1852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 9884 KB Output is correct
2 Correct 834 ms 9808 KB Output is correct
3 Correct 846 ms 9980 KB Output is correct
4 Correct 860 ms 9984 KB Output is correct
5 Correct 823 ms 9920 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 3839 ms 9980 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 59848 KB Output is correct
2 Correct 23 ms 59960 KB Output is correct
3 Correct 21 ms 59960 KB Output is correct
4 Correct 47 ms 60740 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 9884 KB Output is correct
2 Correct 877 ms 9800 KB Output is correct
3 Correct 904 ms 9984 KB Output is correct
4 Correct 860 ms 9984 KB Output is correct
5 Correct 827 ms 9904 KB Output is correct
6 Correct 26 ms 59860 KB Output is correct
7 Correct 24 ms 59896 KB Output is correct
8 Correct 26 ms 59984 KB Output is correct
9 Correct 49 ms 60724 KB Output is correct
10 Correct 16 ms 47280 KB Output is correct
11 Correct 19 ms 47284 KB Output is correct
12 Correct 68 ms 48980 KB Output is correct
13 Correct 17 ms 47328 KB Output is correct
14 Correct 21 ms 47388 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 852 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 1 ms 852 KB Output is correct
23 Correct 1 ms 852 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 53 ms 1808 KB Output is correct
26 Correct 2 ms 848 KB Output is correct
27 Correct 3822 ms 9980 KB Output is correct
28 Runtime error 3103 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 9964 KB Output is correct
2 Correct 844 ms 9800 KB Output is correct
3 Correct 852 ms 9988 KB Output is correct
4 Correct 863 ms 9984 KB Output is correct
5 Correct 840 ms 9900 KB Output is correct
6 Correct 23 ms 59852 KB Output is correct
7 Correct 23 ms 59920 KB Output is correct
8 Correct 23 ms 59916 KB Output is correct
9 Correct 50 ms 60700 KB Output is correct
10 Correct 18 ms 47316 KB Output is correct
11 Correct 18 ms 47312 KB Output is correct
12 Correct 70 ms 48936 KB Output is correct
13 Correct 17 ms 47316 KB Output is correct
14 Correct 17 ms 47292 KB Output is correct
15 Execution timed out 20112 ms 225772 KB Time limit exceeded
16 Halted 0 ms 0 KB -