oj.uz

답안 #780945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780945 2023-07-12T14:54:40 Z NothingXD 웜뱃 (IOI13_wombats) C++17
37 / 100
 3591 ms 21332 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], ptrdp[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 shib = m-1; shib >= 1-m; shib--){
		for (int i = 0; i < m; i++){
			int j = i - shib;
			if (j < 0 || j >= m) continue;
			int l = (j? ptrdp[i][j-1]: 0);
			int r = (i < m? ptrdp[i+1][j]: m-1);
			ptrdp[i][j] = l;
			seg[v][i][j] = seg[v << 1][i][l] + seg[v << 1 | 1][l][j] + ::v[ptr][l];
			for (int k = l+1; k <= r; k++){
				int tmp = seg[v << 1][i][k] + seg[v << 1 | 1][k][j] + ::v[ptr][k];
				if (tmp < seg[v][i][j]){
					seg[v][i][j] = tmp;
					ptrdp[i][j] = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 13032 KB Output is correct
2 Correct 6 ms 13140 KB Output is correct
3 Correct 58 ms 15892 KB Output is correct
4 Correct 6 ms 13140 KB Output is correct
5 Correct 6 ms 13012 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 304 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 53 ms 2788 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 724 ms 984 KB Output is correct
2 Correct 702 ms 968 KB Output is correct
3 Correct 735 ms 984 KB Output is correct
4 Correct 726 ms 980 KB Output is correct
5 Correct 711 ms 980 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 3591 ms 980 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 21204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 724 ms 992 KB Output is correct
2 Correct 709 ms 972 KB Output is correct
3 Correct 736 ms 980 KB Output is correct
4 Correct 730 ms 980 KB Output is correct
5 Correct 724 ms 980 KB Output is correct
6 Incorrect 11 ms 21252 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 727 ms 980 KB Output is correct
2 Correct 711 ms 964 KB Output is correct
3 Correct 734 ms 992 KB Output is correct
4 Correct 731 ms 984 KB Output is correct
5 Correct 717 ms 980 KB Output is correct
6 Incorrect 11 ms 21332 KB Output isn't correct
7 Halted 0 ms 0 KB -