oj.uz

Submission #60369

# Submission time Handle Problem Language Result Execution time Memory
60369 2018-07-24T02:40:16 Z spencercompton Wombats (IOI13_wombats) C++17
9 / 100
 297 ms 19532 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++){
	// 	for(int k = 0; k<c; k++){
	// 		int best = a1[i][0] + bel[ro][0] + a2[0][k];
	// 		for(int j = 1; j<c; j++){
	// 			best = min(best, a1[i][j] + bel[ro][j] + a2[j][k]);
	// 		}
	// 		// 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 24 ms 9336 KB Output is correct
2 Correct 21 ms 9464 KB Output is correct
3 Correct 150 ms 12488 KB Output is correct
4 Correct 23 ms 12488 KB Output is correct
5 Correct 17 ms 12488 KB Output is correct
6 Correct 3 ms 12488 KB Output is correct
7 Correct 3 ms 12488 KB Output is correct
8 Correct 4 ms 12488 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

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