Submission #280293

#	Time	Username	Problem	Language	Result	Execution time	Memory
280293		amoo_safar	Wombats (IOI13_wombats)	C++17	55 / 100	20100 ms	103772 KiB

wombats

#include "wombats.h"

#include <bits/stdc++.h>

using namespace std;

const int MR = 5010;
const int MC = 210;
const int BL = 20;
const int CBL = 256;
const int Inf = 1000000000;

int r, c;
int H[MR][MC], V[MR][MC], ps[MC];

struct node {
	int dp[MC][MC];
};
node seg[CBL << 1];

int opt[MC][MC];

void Merge(int A, int B, int C, int rw){
	memset(seg[A].dp, 31, sizeof seg[A].dp);
	int lc, rc, mn, nw, idx;
	for(int i = 0; i < c; i++){
		for(int j = c - 1; j >= 0; j--){
			lc = (i ? opt[i - 1][j] : 0);
			rc = (j == c - 1 ? c - 1 : opt[i][j + 1]);
			mn = seg[C].dp[i][lc] + V[rw][lc] + seg[B].dp[lc][j];
			idx = lc;
			for(int k = lc + 1; k <= rc; k++){
				nw = seg[C].dp[i][k] + V[rw][k] + seg[B].dp[k][j];
				if(nw < mn){
					mn = nw;
					idx = k;
				}
			}
			opt[i][j] = idx;
			seg[A].dp[i][j] = mn;
		}
	}
}

int tdp[BL][MC];

void BuildRow(int id, int ur, int dr){
	//cerr << "# " << ur << ' ' << dr << '\n';
	int row;
	for(int sc = 0; sc < c; sc ++){
		memset(tdp, 0, sizeof tdp);
		ps[0] = 0;
		for(int i = 1; i < c; i++) ps[i] = ps[i - 1] + H[dr][i - 1];
		
		for(int i = 0; i < c; i++) tdp[0][i] = abs(ps[i] - ps[sc]);

		for(int i = dr - 1; i >= ur; i--){
			row = dr - i;
			ps[0] = 0;
			for(int j = 1; j < c; j++) ps[j] = ps[j - 1] + H[i][j - 1];
			
			int res = Inf;
			for(int j = 0; j < c; j++){
				res = min(res, V[i][j] + tdp[row - 1][j] - ps[j]);
				tdp[row][j] = ps[j] + res;
			}
			res = Inf;
			for(int j = c - 1; j >= 0; j--){
				res = min(res, V[i][j] + tdp[row - 1][j] + ps[j]);
				tdp[row][j] = min(tdp[row][j], res - ps[j]);
			}
		}
		/*
		for(int i = 0; i < c; i++)
			for(int j = 0; j < c; j++)
				seg[id].dp[i][j] = abs(ps[i] - ps[j]); //min(seg[id].dp[i][j]);
		*/
		for(int i = 0; i < c; i++)
			seg[id].dp[sc][i] = tdp[dr - ur][i];
	}
}
void Build(int id, int L, int R){
	if(R - L <= BL){
		BuildRow(id, L, R - 1);
		return ;
	}
	int mid = (L + R) >> 1;
	Build(id << 1, L, mid);
	Build(id << 1 | 1, mid, R);
	Merge(id, id << 1, id << 1 | 1, mid - 1);
}

/*
void Build(){
	memset(dp, 0, sizeof dp);
	//fill(dp[R - 1], dp[R - 1] + C, 0);
	for(int i = R - 2; i >= 0; i--){
		ps[0] = 0;
		for(int j = 1; j < C; j++) ps[j] = ps[j - 1] + H[i][j - 1];
		int res = Inf;
		for(int j = 0; j < C; j++){
			res = min(res, V[i][j] + dp[i + 1][j] - ps[j]);
			dp[i][j] = ps[j] + res;
		}
		res = Inf;
		for(int j = C - 1; j >= 0; j--){
			res = min(res, V[i][j] + dp[i + 1][j] + ps[j]);
			dp[i][j] = res - ps[j];
		}
	}
}
*/
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 - 1; j++)
    		H[i][j] = _H[i][j];
    for(int i = 0; i < r - 1; i++)
    	for(int j = 0; j < c; j++)
    		V[i][j] = _V[i][j];   	
    Build(1, 0, r);
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
	Build(1, 0, r);
    /* ... */
}

void changeV(int P, int Q, int W){
	V[P][Q] = W;
	Build(1, 0, r);
    /* ... */
}

int escape(int V1, int V2) {
    return seg[1].dp[V2][V1];
}

Compilation message (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24