oj.uz

Submission #765100

# Submission time Handle Problem Language Result Execution time Memory
765100 2023-06-24T08:23:26 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 << 2][MAXM][MAXM], opt[MAXM][MAXM];

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[v << 1][x][x] + V[mid][x] + sg[v << 1 | 1][x][y];
			for (int f = 1; f <= m; f++) {
				sg[v][x][y] = min(sg[v][x][y], sg[v << 1][x][f] + V[mid][f] + sg[v << 1 | 1][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;
		build(l, mid, v << 1);
		build(mid + 1, r, v << 1 | 1);
		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, v << 1);
		else update(ind, mid + 1, r, v << 1 | 1);
		
		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 22 ms 47828 KB Output is correct
2 Correct 23 ms 47808 KB Output is correct
3 Correct 75 ms 50628 KB Output is correct
4 Correct 22 ms 47844 KB Output is correct
5 Correct 22 ms 47780 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 308 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 820 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 58 ms 3136 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 849 ms 9952 KB Output is correct
2 Correct 849 ms 9896 KB Output is correct
3 Correct 874 ms 10036 KB Output is correct
4 Correct 850 ms 10056 KB Output is correct
5 Correct 820 ms 9968 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 3797 ms 10052 KB Output is correct
10 Correct 0 ms 308 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 60336 KB Output is correct
2 Correct 28 ms 60284 KB Output is correct
3 Correct 28 ms 60384 KB Output is correct
4 Correct 54 ms 61756 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 9952 KB Output is correct
2 Correct 835 ms 9864 KB Output is correct
3 Correct 850 ms 10072 KB Output is correct
4 Correct 868 ms 10056 KB Output is correct
5 Correct 851 ms 9968 KB Output is correct
6 Correct 29 ms 60332 KB Output is correct
7 Correct 26 ms 60348 KB Output is correct
8 Correct 28 ms 60360 KB Output is correct
9 Correct 66 ms 61800 KB Output is correct
10 Correct 27 ms 47812 KB Output is correct
11 Correct 27 ms 47820 KB Output is correct
12 Correct 80 ms 50632 KB Output is correct
13 Correct 21 ms 47864 KB Output is correct
14 Correct 23 ms 47804 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 824 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 1 ms 852 KB Output is correct
22 Correct 1 ms 724 KB Output is correct
23 Correct 1 ms 852 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 56 ms 3192 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 3800 ms 10140 KB Output is correct
28 Runtime error 3047 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 876 ms 9952 KB Output is correct
2 Correct 829 ms 9860 KB Output is correct
3 Correct 886 ms 10060 KB Output is correct
4 Correct 916 ms 9932 KB Output is correct
5 Correct 834 ms 9964 KB Output is correct
6 Correct 27 ms 60364 KB Output is correct
7 Correct 31 ms 60344 KB Output is correct
8 Correct 28 ms 60364 KB Output is correct
9 Correct 54 ms 61720 KB Output is correct
10 Correct 20 ms 47912 KB Output is correct
11 Correct 22 ms 47808 KB Output is correct
12 Correct 72 ms 50576 KB Output is correct
13 Correct 20 ms 47880 KB Output is correct
14 Correct 20 ms 47856 KB Output is correct
15 Execution timed out 20048 ms 257352 KB Time limit exceeded
16 Halted 0 ms 0 KB -