Submission #103057

#	Time	Username	Problem	Language	Result	Execution time	Memory
103057		wilwxk	Wombats (IOI13_wombats)	C++11	100 / 100	19373 ms	158968 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXC=202;
const int MAXR=5002;
const int SQRN=12;
const int TAM=(MAXR/SQRN)*3+4;

int seg[TAM][MAXC][MAXC];
short v[MAXR][MAXC], h[MAXR][MAXC];
int ps[MAXR][MAXC];
int bini[TAM], bfim[TAM];
short bid[MAXR];
int nn, rr, cc;
int vago, vago2;

//anda de da coluna ini ate coluna fim na linha "linha"
int anda(int linha, int ini, int fim) {
	if(fim<ini) swap(ini, fim);
	if(ini==fim) return 0;
	int val=ps[linha][fim-1];
	if(ini>0) val-=ps[linha][ini-1];
	return val;
}

//calcula juncao dos blocos sind2 e sind3 e coloca no sind
//computa de todos os pontos do sind2 ate o fixo no ponto 3
//ponte sao as estradas que ligam os blocos sind2 e sind3
void calc(int sind, int sind2, int sind3, int ponte, int fixo, int ini, int fim, int rini, int rfim) {
	if(fim<ini) return;
	int mid=(ini+fim)/2;

	int opt=rini; int melhor=1e9;
	for(int i=rini; i<=rfim; i++) {
		int val=seg[sind2][mid][i]+seg[sind3][i][fixo]+v[ponte][i];
		// printf("  vai de %d para %d testando %d > %d %d %d\n", mid, fixo, i, seg[sind2][mid][i], v[ponte][i], seg[sind3][i][fixo]);
		if(val<melhor) melhor=val, opt=i;
	}

	// printf("fixo = %d && opt de %d = %d && melhor=%d\n", fixo, mid, opt, melhor);
	seg[sind][mid][fixo]=melhor;
	calc(sind, sind2, sind3, ponte, fixo, ini, mid-1, rini, opt);
	calc(sind, sind2, sind3, ponte, fixo, mid+1, fim, opt, rfim);
}

//computa o bloco x
void computa(int x) {
	int ini=bini[x]; int fim=bfim[x];

	for(int i=0; i<cc; i++) for(int j=i; j<cc; j++) seg[x][i][j]=seg[x][j][i]=anda(ini, i, j);

	for(int linha=ini+1; linha<=fim; linha++) {
		for(int i=0; i<cc; i++) for(int j=0; j<cc; j++) seg[vago][i][j]=seg[x][i][j];
		for(int i=0; i<cc; i++) for(int j=i; j<cc; j++) seg[vago2][i][j]=seg[vago2][j][i]=anda(linha, i, j);
		for(int fixo=0; fixo<cc; fixo++) calc(x, vago, vago2, linha-1, fixo, 0, cc-1, 0, cc-1);
	}
}

void build(int sind, int ini, int fim) {
	// printf("%d = [%d, %d]\n", sind, ini, fim);
	if(ini==fim) {
		bini[sind]=(ini-1)*SQRN;
		bfim[sind]=bini[sind]+SQRN-1;
		bfim[sind]=min(bfim[sind], rr-1);
		computa(sind);
		return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	build(e, ini, m); build(d, m+1, fim);
	bini[sind]=bini[e]; bfim[sind]=bfim[d];
	for(int i=0; i<cc; i++) calc(sind, e, d, bfim[e], i, 0, cc-1, 0, cc-1);
}

void update(int sind, int ini, int fim, int qind) {
	if(qind<ini||qind>fim) return;
	if(ini==fim) {
		computa(sind);
		return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	update(e, ini, m, qind); update(d, m+1, fim, qind);
	for(int i=0; i<cc; i++) calc(sind, e, d, bfim[e], i, 0, cc-1, 0, cc-1);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	rr=R; cc=C;
	for(int i=0; i<cc; i++) for(int j=0; j<rr-1; j++) v[j][i]=V[j][i];
	for(int i=0; i<rr; i++) {
		for(int j=0; j<cc-1; j++) {
			h[i][j]=H[i][j];
			if(j!=0) ps[i][j]=ps[i][j-1]+h[i][j];
			else ps[i][j]=h[i][j];
		}
	}
	vago=TAM-2; vago2=TAM-1;

	for(int i=0; i<rr; i++) bid[i]=i/SQRN+1;
	nn=bid[rr-1];
	build(1, 1, nn);
}

void changeH(int P, int Q, int W) {
    h[P][Q]=W;
    for(int i=0; i<cc-1; i++) {
    	ps[P][i]=h[P][i];
    	if(i!=0) ps[P][i]+=ps[P][i-1];
    }
    update(1, 1, nn, bid[P]);
}

void changeV(int P, int Q, int W) {
    v[P][Q]=W;
    update(1, 1, nn, bid[P]);
}

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

Compilation message (stderr)

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