oj.uz

Submission #764126

# Submission time Handle Problem Language Result Execution time Memory
764126 2023-06-23T07:30:48 Z NothingXD Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 55624 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 = 100;
const int inf = 1e9;
int n, m, h[maxn][maxm], v[maxn][maxm], dp[maxn][maxm], val[50][maxm][maxm], seg[210][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);
	}
	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++){
				seg[v][i][j] = min(seg[v][i][j], seg[v << 1][i][k] + seg[v << 1 | 1][k][j] + ::v[mid*sq-1][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 5 ms 13012 KB Output is correct
2 Correct 5 ms 13012 KB Output is correct
3 Correct 57 ms 15816 KB Output is correct
4 Correct 7 ms 13140 KB Output is correct
5 Correct 7 ms 13012 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 312 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 54 ms 1340 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 720 ms 892 KB Output is correct
2 Correct 710 ms 888 KB Output is correct
3 Correct 728 ms 900 KB Output is correct
4 Correct 728 ms 900 KB Output is correct
5 Correct 711 ms 976 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 212 KB Output is correct
9 Correct 3594 ms 852 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 11 ms 21160 KB Output is correct
2 Correct 11 ms 21204 KB Output is correct
3 Correct 11 ms 21204 KB Output is correct
4 Correct 38 ms 22632 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 896 KB Output is correct
2 Correct 712 ms 892 KB Output is correct
3 Correct 730 ms 900 KB Output is correct
4 Correct 732 ms 852 KB Output is correct
5 Correct 713 ms 900 KB Output is correct
6 Correct 11 ms 21232 KB Output is correct
7 Correct 12 ms 21296 KB Output is correct
8 Correct 11 ms 21204 KB Output is correct
9 Correct 43 ms 22608 KB Output is correct
10 Correct 6 ms 13124 KB Output is correct
11 Correct 6 ms 13048 KB Output is correct
12 Correct 60 ms 15788 KB Output is correct
13 Correct 7 ms 13140 KB Output is correct
14 Correct 7 ms 13032 KB Output is correct
15 Correct 1 ms 340 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 468 KB Output is correct
19 Correct 1 ms 436 KB Output is correct
20 Correct 1 ms 440 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 440 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 67 ms 2760 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3632 ms 976 KB Output is correct
28 Correct 7694 ms 37420 KB Output is correct
29 Correct 7313 ms 31216 KB Output is correct
30 Correct 7376 ms 31180 KB Output is correct
31 Correct 7511 ms 39116 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 892 KB Output is correct
2 Correct 705 ms 972 KB Output is correct
3 Correct 727 ms 900 KB Output is correct
4 Correct 728 ms 912 KB Output is correct
5 Correct 713 ms 908 KB Output is correct
6 Correct 10 ms 21204 KB Output is correct
7 Correct 10 ms 21180 KB Output is correct
8 Correct 10 ms 21312 KB Output is correct
9 Correct 38 ms 22668 KB Output is correct
10 Correct 6 ms 13012 KB Output is correct
11 Correct 6 ms 13012 KB Output is correct
12 Correct 58 ms 15800 KB Output is correct
13 Correct 6 ms 13040 KB Output is correct
14 Correct 6 ms 13124 KB Output is correct
15 Correct 4367 ms 55624 KB Output is correct
16 Execution timed out 20007 ms 54748 KB Time limit exceeded
17 Halted 0 ms 0 KB -