oj.uz

Submission #764121

# Submission time Handle Problem Language Result Execution time Memory
764121 2023-06-23T07:27:25 Z NothingXD Wombats (IOI13_wombats) C++17
28 / 100
 3705 ms 21292 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]);
			}
		}
	}
}

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13012 KB Output is correct
2 Incorrect 7 ms 13012 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 436 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 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 56 ms 2860 KB Output is correct
12 Correct 1 ms 440 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 892 KB Output is correct
2 Correct 722 ms 964 KB Output is correct
3 Correct 747 ms 984 KB Output is correct
4 Correct 750 ms 984 KB Output is correct
5 Correct 733 ms 980 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 304 KB Output is correct
9 Correct 3705 ms 972 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 892 KB Output is correct
2 Correct 725 ms 960 KB Output is correct
3 Correct 750 ms 976 KB Output is correct
4 Correct 749 ms 980 KB Output is correct
5 Correct 735 ms 980 KB Output is correct
6 Incorrect 10 ms 21204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 892 KB Output is correct
2 Correct 734 ms 964 KB Output is correct
3 Correct 765 ms 976 KB Output is correct
4 Correct 757 ms 1000 KB Output is correct
5 Correct 745 ms 980 KB Output is correct
6 Incorrect 11 ms 21292 KB Output isn't correct
7 Halted 0 ms 0 KB -