oj.uz

Submission #60380

# Submission time Handle Problem Language Result Execution time Memory
60380 2018-07-24T04:23:32 Z spencercompton Wombats (IOI13_wombats) C++17
100 / 100
 14617 ms 218488 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
int bel[5000][200];
int rig[5000][200];
int r, c;
vector<vector<int> > get1(int a){
	// cout << "BEG " << endl;
	vector<vector<int> > ret;
	for(int i = 0; i<c; i++){
		vector<int> now;
		now.resize(c);
		int sum = 0;
		for(int j = i+1; j<c; j++){
			sum += rig[a][j-1];
			now[j] = sum;
		}
		sum = 0;
		for(int j = i-1; j>=0; j--){
			sum += rig[a][j];
			now[j] = sum;
		}
		ret.push_back(now);
	}
	// cout << "END " << endl;
	return ret;
}
vector<int> cur;
vector<vector<int> > a1;
vector<vector<int> > a2;
int beg;
int ro;
void go(int l, int r, int lo, int hi){
	if(l>r){
		return;
	}
	int m = (l+r)/2;
	int best = lo;
	int val = a1[beg][best] + a2[best][m] + bel[ro][best];
	for(int i = lo+1; i<=hi; i++){
		int here = a1[beg][i] + a2[i][m] + bel[ro][i];
		if(here<val){
			val = here;
			best = i;
		}
	}
	cur[m] = val;
	go(l,m-1,lo,best);
	go(m+1,r,best,hi);
}
vector<vector<int> > comb(vector<vector<int> > a, vector<vector<int> > b){
	vector<vector<int> > ret;
	cur.resize(c);
	a1 = a;
	a2 = b;
	for(int i = 0; i<c; i++){
		beg = i;
		go(0,c-1,0,c-1);
		ret.push_back(cur);
	}
	return ret;
 
	// vector<vector<int> > ret;
	// cur.resize(c);
	// a1 = a;
	// a2 = b;
	// for(int i = 0; i<c; i++){
	// 	int prev = -1;
	// 	for(int k = 0; k<c; k++){
	// 		int best = a1[i][0] + bel[ro][0] + a2[0][k];
	// 		int noww = 0;
	// 		for(int j = 1; j<c; j++){
	// 			int cv =  a1[i][j] + bel[ro][j] + a2[j][k];
	// 			if(cv<best){
	// 				noww = j;
	// 				best = cv;
	// 			}
	// 		}
	// 		assert(noww>=prev);
	// 		prev = noww;
	// 		// cout << "@ " << best << " " << i << " " << k << endl;
	// 		cur[k] = best;
	// 	}
	// 	ret.push_back(cur);
	// }
	// return ret;
}
vector<vector<int> > brute(int s, int e){
	int rows = e-s+1;
	vector<int> all[rows][c];
	vector<vector<int> > bot = get1(e);
	for(int i = 0; i<c; i++){
		all[rows-1][i] = bot[i];
	}
	for(int i = rows-2; i>=0; i--){
		for(int j = 0; j<c; j++){
			for(int k = 0; k<c; k++){
				all[i][j].push_back(all[i+1][j][k]+bel[s+i][j]);
			}
		}
		for(int j = 1; j<c; j++){
			for(int k = 0; k<c; k++){
				all[i][j][k] = min(all[i][j][k],all[i][j-1][k]+rig[s+i][j-1]);
			}
		}
		for(int j = c-2; j>=0; j--){
			for(int k = 0; k<c; k++){
				all[i][j][k] = min(all[i][j][k],all[i][j+1][k]+rig[s+i][j]);
			}
		}
	}
	vector<vector<int> > ret;
	for(int i = 0; i<c; i++){
		ret.push_back(all[0][i]);
	}
	return ret;
}
class Node{
public:
	int s, e;
	Node *l, *r;
	bool leaf;
	vector<vector<int> > ar;
	Node (int a, int b){
		s = a;
		e = b;
		leaf = (e-s+1) <= 16;
		if(s==e){
			ar = get1(s);
			l = NULL;
			r = NULL;
		}
		else if(leaf){
			ar = brute(s,e);
			l = NULL;
			r = NULL;
		}
		else{
			l = new Node(s,(s+e)/2);
			r = new Node((s+e)/2+1,e);
			ro = l->e;
			ar = comb(l->ar,r->ar);
		}
		// cout << "FOR " << a << " - " << b << endl;
		// for(int i = 0; i<c; i++){
		// 	for(int j = 0; j<c; j++){
		// 		// cout << i << " to " << j << " " << ar[i][j] << endl;
		// 	}
		// }
	}
	void upd(int ind){
		if(s==e){
			ar = get1(s);
			return;
		}
		if(leaf){
			ar = brute(s,e);
			return;
		}
		if(ind<=(s+e)/2){
			l->upd(ind);
		}
		else{
			r->upd(ind);
		}
		ro = l->e;
		ar = comb(l->ar,r->ar);
	}
};
Node *t;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R;
	c = C;
	for(int i = 0; i<r; i++){
		for(int j =0 ; j<c; j++){
			if(i+1<r){
				bel[i][j] = V[i][j];
				// cout << bel[i][j] << " ";
			}
			if(j+1<c){
				rig[i][j] = H[i][j];
			}
		}
		// cout << endl;
	}
	t = new Node(0,r-1);
}
 
void changeH(int P, int Q, int W) {
	// cout << "UPDATE " << P << endl;
	rig[P][Q] = W;
	// t = new Node(0,c-1);
	t->upd(P);
}
 
void changeV(int P, int Q, int W) {
	// cout << "QED " << P << endl;
	bel[P][Q] = W;
	// t = new Node(0,c-1);
	t->upd(P);
}
 
int escape(int V1, int V2) {
	return t->ar[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]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8312 KB Output is correct
2 Correct 17 ms 8384 KB Output is correct
3 Correct 98 ms 9896 KB Output is correct
4 Correct 13 ms 9896 KB Output is correct
5 Correct 16 ms 9896 KB Output is correct
6 Correct 2 ms 9896 KB Output is correct
7 Correct 2 ms 9896 KB Output is correct
8 Correct 2 ms 9896 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9896 KB Output is correct
2 Correct 3 ms 9896 KB Output is correct
3 Correct 4 ms 9896 KB Output is correct
4 Correct 4 ms 9896 KB Output is correct
5 Correct 4 ms 9896 KB Output is correct
6 Correct 3 ms 9896 KB Output is correct
7 Correct 5 ms 9896 KB Output is correct
8 Correct 3 ms 9896 KB Output is correct
9 Correct 3 ms 9896 KB Output is correct
10 Correct 5 ms 9896 KB Output is correct
11 Correct 139 ms 9896 KB Output is correct
12 Correct 4 ms 9896 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 9896 KB Output is correct
2 Correct 250 ms 9896 KB Output is correct
3 Correct 292 ms 9896 KB Output is correct
4 Correct 418 ms 9896 KB Output is correct
5 Correct 272 ms 9896 KB Output is correct
6 Correct 3 ms 9896 KB Output is correct
7 Correct 3 ms 9896 KB Output is correct
8 Correct 3 ms 9896 KB Output is correct
9 Correct 1363 ms 9896 KB Output is correct
10 Correct 3 ms 9896 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 17308 KB Output is correct
2 Correct 31 ms 17308 KB Output is correct
3 Correct 30 ms 17332 KB Output is correct
4 Correct 80 ms 18088 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 18088 KB Output is correct
2 Correct 216 ms 18088 KB Output is correct
3 Correct 283 ms 18088 KB Output is correct
4 Correct 264 ms 18088 KB Output is correct
5 Correct 265 ms 18088 KB Output is correct
6 Correct 31 ms 18088 KB Output is correct
7 Correct 31 ms 18088 KB Output is correct
8 Correct 22 ms 18088 KB Output is correct
9 Correct 68 ms 18136 KB Output is correct
10 Correct 12 ms 18136 KB Output is correct
11 Correct 11 ms 18136 KB Output is correct
12 Correct 110 ms 18136 KB Output is correct
13 Correct 15 ms 18136 KB Output is correct
14 Correct 16 ms 18136 KB Output is correct
15 Correct 2 ms 18136 KB Output is correct
16 Correct 2 ms 18136 KB Output is correct
17 Correct 3 ms 18136 KB Output is correct
18 Correct 4 ms 18136 KB Output is correct
19 Correct 3 ms 18136 KB Output is correct
20 Correct 3 ms 18136 KB Output is correct
21 Correct 3 ms 18136 KB Output is correct
22 Correct 4 ms 18136 KB Output is correct
23 Correct 3 ms 18136 KB Output is correct
24 Correct 3 ms 18136 KB Output is correct
25 Correct 143 ms 18136 KB Output is correct
26 Correct 4 ms 18136 KB Output is correct
27 Correct 1109 ms 18136 KB Output is correct
28 Correct 3177 ms 67512 KB Output is correct
29 Correct 3232 ms 67512 KB Output is correct
30 Correct 3800 ms 67512 KB Output is correct
31 Correct 3614 ms 76488 KB Output is correct
32 Correct 4 ms 76488 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 76488 KB Output is correct
2 Correct 351 ms 76488 KB Output is correct
3 Correct 299 ms 76488 KB Output is correct
4 Correct 390 ms 76488 KB Output is correct
5 Correct 333 ms 76488 KB Output is correct
6 Correct 33 ms 76488 KB Output is correct
7 Correct 31 ms 76488 KB Output is correct
8 Correct 31 ms 76488 KB Output is correct
9 Correct 103 ms 76488 KB Output is correct
10 Correct 18 ms 76488 KB Output is correct
11 Correct 13 ms 76488 KB Output is correct
12 Correct 141 ms 76488 KB Output is correct
13 Correct 14 ms 76488 KB Output is correct
14 Correct 17 ms 76488 KB Output is correct
15 Correct 4111 ms 204120 KB Output is correct
16 Correct 14269 ms 212588 KB Output is correct
17 Correct 4 ms 212588 KB Output is correct
18 Correct 4 ms 212588 KB Output is correct
19 Correct 2 ms 212588 KB Output is correct
20 Correct 3 ms 212588 KB Output is correct
21 Correct 4 ms 212588 KB Output is correct
22 Correct 4 ms 212588 KB Output is correct
23 Correct 4 ms 212588 KB Output is correct
24 Correct 4 ms 212588 KB Output is correct
25 Correct 5 ms 212588 KB Output is correct
26 Correct 3 ms 212588 KB Output is correct
27 Correct 132 ms 212588 KB Output is correct
28 Correct 4 ms 212588 KB Output is correct
29 Correct 1451 ms 212588 KB Output is correct
30 Correct 3259 ms 212588 KB Output is correct
31 Correct 12222 ms 212588 KB Output is correct
32 Correct 11861 ms 212588 KB Output is correct
33 Correct 3141 ms 212588 KB Output is correct
34 Correct 14033 ms 212588 KB Output is correct
35 Correct 3653 ms 212588 KB Output is correct
36 Correct 14617 ms 212588 KB Output is correct
37 Correct 3347 ms 212588 KB Output is correct
38 Correct 13481 ms 218488 KB Output is correct
39 Correct 3 ms 218488 KB Output is correct
40 Correct 14268 ms 218488 KB Output is correct