oj.uz

Submission #389166

# Submission time Handle Problem Language Result Execution time Memory
389166 2021-04-13T19:04:24 Z crackersamdjam Wombats (IOI13_wombats) C++17
100 / 100
 8950 ms 189000 KB 
#ifndef LOCAL
#pragma GCC optimize("O3","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
#endif

#ifndef LOCAL
#ifndef ONLINE_JUDGE
#include "wombats.h"
#endif
#endif
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif

using namespace std;
constexpr int MM = 5001, NN = 201, SZ = 10;

#define nm ((nl+nr)/2)
#define lc (rt<<1)
#define rc (rt<<1|1)
#define npm int nl = 0, int nr = n-1, int rt = 1
#define lpm nl, nm, lc
#define rpm nm+1, nr, rc

int t[MM*3/SZ][NN][NN];
int n, m;
int H[MM][NN];
int V[MM][NN];

void go(int pre[NN], int cur[NN][NN], int res[NN], int l, int r, int ls, int rs){
	if(l > r) return;
	int mm = l+r>>1, id = ls;
	res[mm] = 1e9;
	for(int i = ls; i <= rs; i++){
		int v = pre[i]+cur[i][mm];
		if(v < res[mm]){
			res[mm] = v;
			id = i;
		}
	}
	go(pre, cur, res, l, mm-1, ls, id);
	go(pre, cur, res, mm+1, r, id, rs);
}

void pull(int rt, int nl, int nr){
	for(int st = 0; st < m; st++)
		go(t[lc][st], t[rc], t[rt][st], 0, m-1, 0, m-1);
}

void child(int u, int d, int dp[NN][NN]){
	int pre[NN][NN]; memset(pre, 0x3f, sizeof pre);
	for(int i = 0; i < m; i++)
		pre[i][i] = 0;

	for(int k = u; k <= d; k++){
		for(int i = 0; i < m; i++){
			for(int j = 0; j < m; j++)
				dp[i][j] = pre[i][j] + (k ? V[k-1][j] : 0);

			for(int j = 1; j < m; j++)
				dp[i][j] = min(dp[i][j], dp[i][j-1] + H[k][j-1]);
			for(int j = m-2; j >= 0; j--)
				dp[i][j] = min(dp[i][j], dp[i][j+1] + H[k][j]);

			for(int j = 0; j < m; j++)
				pre[i][j] = dp[i][j];
		}
	}
	// pr("ch", u, d);
	// for(int i = 0; i < m; i++){
	// 	for(int j = 0; j < m; j++)
	// 		cerr<<dp[i][j]<<' ';
	// 	cerr<<endl;
	// }
}

void build(npm){
	if(nr-nl <= SZ){
		child(nl, nr, t[rt]);
		return;
	}
	build(lpm); build(rpm);
	pull(rt, nl, nr);
}

void update(int i, npm){
	if(nr-nl <= SZ){
		child(nl, nr, t[rt]);
		return;
	}
	i <= nm ? update(i, lpm) : update(i, rpm);
	pull(rt, nl, nr);
}

void init(int R, int C, int _H[5000][200], int _V[5000][200]){
	n = R, m = C;
	assert(n < MM);
	assert(m < NN);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			H[i][j] = _H[i][j];
			V[i][j] = _V[i][j];
		}
	}
	build();
}

void changeH(int i, int j, int v){
	H[i][j] = v;
	update(i);
}

void changeV(int i, int j, int v){
	V[i][j] = v;
	update(i+1);
}

int escape(int a, int b){
	return t[1][a][b];
}

#ifdef LOCAL

int _H[5000][200], _V[5000][200];

int main(){
	// int aa[5000][200] = {{0,2,5}, {7,1,1}, {0,4,0}};
	// int bb[5000][200] = {{0,0,0,2}, {0,3,4,7}};
	// init(3, 4, aa, bb);
	int _n, _m;
	cin>>_n>>_m;
	for(int i = 0; i < _n; i++){
		for(int j = 0; j < _m-1; j++){
			cin>>_H[i][j];
		}
	}
	for(int i = 0; i < _n-1; i++){
		for(int j=  0; j < _m; j++){
			cin>>_V[i][j];
		}
	}
	init(_n, _m, _H, _V);
	// pr("_____________");
	int _q; cin>>_q;
	while(_q--){
		int a, b, c, d;
		cin>>a>>b>>c;
		if(a == 1){
			cin>>d;
			changeH(b, c, d);
		}
		else if(a == 2){
			cin>>d;
			changeV(b, c, d);
		}
		else if(a == 3){
			cout<<escape(b, c)<<'\n';
		}
		else abort();
	}
	// cout<<escape(2,1)<<'\n';
	// cout<<escape(3,3)<<'\n';
	// changeV(0,0,5);
	// changeH(1,1,6);	
	// cout<<escape(2,1)<<'\n';
}
#endif

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;
      |      ^~~
wombats.cpp:3: warning: ignoring #pragma GCC option [-Wunknown-pragmas]
    3 | #pragma GCC option("arch=native","tune=native","no-zero-upper")
      | 
wombats.cpp: In function 'void go(int*, int (*)[201], int*, int, int, int, int)':
wombats.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int mm = l+r>>1, id = ls;
      |           ~^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16844 KB Output is correct
2 Correct 15 ms 16592 KB Output is correct
3 Correct 95 ms 19420 KB Output is correct
4 Correct 16 ms 16608 KB Output is correct
5 Correct 16 ms 16536 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 78 ms 1492 KB Output is correct
12 Correct 1 ms 588 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 3276 KB Output is correct
2 Correct 142 ms 3276 KB Output is correct
3 Correct 178 ms 3412 KB Output is correct
4 Correct 183 ms 3408 KB Output is correct
5 Correct 171 ms 3400 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 671 ms 3524 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21372 KB Output is correct
2 Correct 19 ms 21428 KB Output is correct
3 Correct 19 ms 21380 KB Output is correct
4 Correct 66 ms 22688 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 3324 KB Output is correct
2 Correct 152 ms 3376 KB Output is correct
3 Correct 196 ms 3416 KB Output is correct
4 Correct 177 ms 3420 KB Output is correct
5 Correct 171 ms 3404 KB Output is correct
6 Correct 20 ms 21432 KB Output is correct
7 Correct 19 ms 21488 KB Output is correct
8 Correct 20 ms 21344 KB Output is correct
9 Correct 60 ms 22776 KB Output is correct
10 Correct 15 ms 16644 KB Output is correct
11 Correct 15 ms 16692 KB Output is correct
12 Correct 93 ms 19444 KB Output is correct
13 Correct 15 ms 16588 KB Output is correct
14 Correct 15 ms 16680 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 1 ms 588 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 1 ms 588 KB Output is correct
25 Correct 79 ms 2864 KB Output is correct
26 Correct 1 ms 588 KB Output is correct
27 Correct 679 ms 3408 KB Output is correct
28 Correct 2017 ms 104680 KB Output is correct
29 Correct 2044 ms 101740 KB Output is correct
30 Correct 2128 ms 101592 KB Output is correct
31 Correct 2174 ms 106356 KB Output is correct
32 Correct 1 ms 460 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 3328 KB Output is correct
2 Correct 144 ms 3276 KB Output is correct
3 Correct 177 ms 3404 KB Output is correct
4 Correct 175 ms 3416 KB Output is correct
5 Correct 174 ms 3404 KB Output is correct
6 Correct 19 ms 21324 KB Output is correct
7 Correct 19 ms 21324 KB Output is correct
8 Correct 19 ms 21380 KB Output is correct
9 Correct 61 ms 22704 KB Output is correct
10 Correct 15 ms 16588 KB Output is correct
11 Correct 15 ms 16616 KB Output is correct
12 Correct 111 ms 19428 KB Output is correct
13 Correct 16 ms 16588 KB Output is correct
14 Correct 15 ms 16660 KB Output is correct
15 Correct 2651 ms 187768 KB Output is correct
16 Correct 8950 ms 189000 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 1 ms 588 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 1 ms 588 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 1 ms 588 KB Output is correct
27 Correct 79 ms 2884 KB Output is correct
28 Correct 1 ms 588 KB Output is correct
29 Correct 717 ms 3428 KB Output is correct
30 Correct 2011 ms 104588 KB Output is correct
31 Correct 7863 ms 186532 KB Output is correct
32 Correct 7908 ms 186544 KB Output is correct
33 Correct 2069 ms 101740 KB Output is correct
34 Correct 8392 ms 183012 KB Output is correct
35 Correct 2134 ms 101444 KB Output is correct
36 Correct 8342 ms 182972 KB Output is correct
37 Correct 2156 ms 106356 KB Output is correct
38 Correct 8320 ms 186808 KB Output is correct
39 Correct 1 ms 460 KB Output is correct
40 Correct 8790 ms 183108 KB Output is correct