oj.uz

Submission #60371

# Submission time Handle Problem Language Result Execution time Memory
60371 2018-07-24T02:44:47 Z spencercompton Wombats (IOI13_wombats) C++17
55 / 100
 5044 ms 263168 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;
}
class Node{
public:
	int s, e;
	Node *l, *r;
	vector<vector<int> > ar;
	Node (int a, int b){
		s = a;
		e = b;
		if(s==e){
			ar = get1(s);
			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(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 16 ms 9336 KB Output is correct
2 Correct 21 ms 9444 KB Output is correct
3 Correct 122 ms 11184 KB Output is correct
4 Correct 24 ms 11184 KB Output is correct
5 Correct 16 ms 11184 KB Output is correct
6 Correct 2 ms 11184 KB Output is correct
7 Correct 2 ms 11184 KB Output is correct
8 Correct 3 ms 11184 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 11184 KB Output is correct
2 Correct 232 ms 11184 KB Output is correct
3 Correct 408 ms 11184 KB Output is correct
4 Correct 358 ms 11184 KB Output is correct
5 Correct 283 ms 11184 KB Output is correct
6 Correct 3 ms 11184 KB Output is correct
7 Correct 3 ms 11184 KB Output is correct
8 Correct 2 ms 11184 KB Output is correct
9 Correct 1000 ms 11188 KB Output is correct
10 Correct 3 ms 11188 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 19016 KB Output is correct
2 Correct 28 ms 19016 KB Output is correct
3 Correct 35 ms 19016 KB Output is correct
4 Correct 107 ms 19912 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 19912 KB Output is correct
2 Correct 233 ms 19912 KB Output is correct
3 Correct 319 ms 19912 KB Output is correct
4 Correct 359 ms 19912 KB Output is correct
5 Correct 402 ms 19912 KB Output is correct
6 Correct 41 ms 19912 KB Output is correct
7 Correct 41 ms 19912 KB Output is correct
8 Correct 41 ms 19912 KB Output is correct
9 Correct 108 ms 20012 KB Output is correct
10 Correct 17 ms 20012 KB Output is correct
11 Correct 21 ms 20012 KB Output is correct
12 Correct 114 ms 20012 KB Output is correct
13 Correct 25 ms 20012 KB Output is correct
14 Correct 22 ms 20012 KB Output is correct
15 Correct 2 ms 20012 KB Output is correct
16 Correct 3 ms 20012 KB Output is correct
17 Correct 3 ms 20012 KB Output is correct
18 Correct 5 ms 20012 KB Output is correct
19 Correct 4 ms 20012 KB Output is correct
20 Correct 5 ms 20012 KB Output is correct
21 Correct 4 ms 20012 KB Output is correct
22 Correct 4 ms 20012 KB Output is correct
23 Correct 4 ms 20012 KB Output is correct
24 Correct 4 ms 20012 KB Output is correct
25 Correct 150 ms 20012 KB Output is correct
26 Correct 4 ms 20012 KB Output is correct
27 Correct 1288 ms 20012 KB Output is correct
28 Runtime error 5044 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 312 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -