oj.uz

Submission #764163

# Submission time Handle Problem Language Result Execution time Memory
764163 2023-06-23T08:06:33 Z NothingXD Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 24308 KB 
#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 5e3 + 10;
const int maxm = 200 + 10;
const int sq = 715;
const int inf = 1e9;
int n, m, h[maxn][maxm], v[maxn][maxm], dp[maxn][maxm], val[10][maxm][maxm], seg[40][maxm][maxm];

void change(int v, int l, int r, int idx){
	if (l + 1 == r){
		for (int i = 0; i < m; i++){
			for (int j = 0; j < m; j++){
				seg[v][i][j] = val[l][i][j];
			}
		}
		return;
	}
	int mid = (l + r) >> 1;
	if (idx < mid){
		change(v << 1, l, mid, idx);
	}
	else{
		change(v << 1 | 1, mid, r, idx);
	}
	int ptr = mid * sq - 1;
	for (int i = 0; i < m; i++){
		for (int j = 0; j < m; j++){
			seg[v][i][j] = inf;
		}
		for (int k = 0; k < m; k++){
			for (int j = 0; j < m; j++){
				seg[v][i][j] = min(seg[v][i][j], seg[v << 1][i][k] + seg[v << 1 | 1][k][j] + ::v[ptr][k]);
			}
		}
	}
}

inline void update(int r){
	for (int i = 1; i < m; i++){
		dp[r][i] = min(dp[r][i], dp[r][i-1] + h[r][i-1]);
	}
	for (int i = m-2; ~i; i--){
		dp[r][i] = min(dp[r][i], dp[r][i+1] + h[r][i]);
	}
}

inline void build(int blc){
	for (int i = 0; i < m; i++){
		for (int j = 0; j < m; j++){
			if (i == j) dp[blc*sq][j] = 0;
			else dp[blc*sq][j] = inf;
		}
		update(blc*sq);
		int idx = min((blc+1)*sq, n) - 1;
		for (int j = blc*sq+1; j <= idx; j++){
			for (int k = 0; k < m; k++){
				dp[j][k] = dp[j-1][k] + v[j-1][k];
			}
			update(j);
		}
		for (int j = 0; j < m; j++){
			val[blc][i][j] = dp[idx][j];
		}
	}
	change(1, 0, (n-1)/sq+1, blc);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R, m = C;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m-1; j++){
			h[i][j] = H[i][j];
		}
	}
	for (int i = 0; i < n-1; i++){
		for (int j = 0; j < m; j++){
			v[i][j] = V[i][j];
		}
	}
	for (int i = 0; i <= (n-1)/sq; i++){
		build(i);
	}
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
	build(P/sq);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
	build(P/sq);
}

int escape(int V1, int V2) {
    return seg[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]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12500 KB Output is correct
2 Correct 6 ms 12524 KB Output is correct
3 Correct 58 ms 14108 KB Output is correct
4 Correct 8 ms 12428 KB Output is correct
5 Correct 6 ms 12500 KB Output is correct
6 Correct 0 ms 212 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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 53 ms 1448 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 888 KB Output is correct
2 Correct 704 ms 900 KB Output is correct
3 Correct 725 ms 892 KB Output is correct
4 Correct 737 ms 852 KB Output is correct
5 Correct 712 ms 980 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 3594 ms 980 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20500 KB Output is correct
2 Correct 18 ms 20536 KB Output is correct
3 Correct 17 ms 20516 KB Output is correct
4 Correct 57 ms 21316 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 884 KB Output is correct
2 Correct 706 ms 888 KB Output is correct
3 Correct 726 ms 896 KB Output is correct
4 Correct 736 ms 904 KB Output is correct
5 Correct 711 ms 912 KB Output is correct
6 Correct 16 ms 20484 KB Output is correct
7 Correct 17 ms 20572 KB Output is correct
8 Correct 16 ms 20572 KB Output is correct
9 Correct 43 ms 21308 KB Output is correct
10 Correct 6 ms 12500 KB Output is correct
11 Correct 7 ms 12500 KB Output is correct
12 Correct 57 ms 14056 KB Output is correct
13 Correct 6 ms 12500 KB Output is correct
14 Correct 10 ms 12456 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 53 ms 1396 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3583 ms 900 KB Output is correct
28 Execution timed out 20066 ms 22340 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 892 KB Output is correct
2 Correct 707 ms 852 KB Output is correct
3 Correct 729 ms 976 KB Output is correct
4 Correct 724 ms 900 KB Output is correct
5 Correct 711 ms 852 KB Output is correct
6 Correct 16 ms 20564 KB Output is correct
7 Correct 20 ms 20560 KB Output is correct
8 Correct 17 ms 20564 KB Output is correct
9 Correct 45 ms 21324 KB Output is correct
10 Correct 6 ms 12500 KB Output is correct
11 Correct 6 ms 12500 KB Output is correct
12 Correct 59 ms 14036 KB Output is correct
13 Correct 7 ms 12500 KB Output is correct
14 Correct 6 ms 12500 KB Output is correct
15 Correct 2563 ms 23932 KB Output is correct
16 Execution timed out 20051 ms 24308 KB Time limit exceeded
17 Halted 0 ms 0 KB -