oj.uz

Submission #103057

# Submission time Handle Problem Language Result Execution time Memory
103057 2019-03-29T00:56:12 Z wilwxk Wombats (IOI13_wombats) C++11
100 / 100
 19373 ms 158968 KB 
#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

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 10 ms 9984 KB Output is correct
2 Correct 16 ms 9856 KB Output is correct
3 Correct 75 ms 11512 KB Output is correct
4 Correct 11 ms 9984 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 2424 KB Output is correct
2 Correct 357 ms 2296 KB Output is correct
3 Correct 509 ms 2424 KB Output is correct
4 Correct 396 ms 2296 KB Output is correct
5 Correct 376 ms 2296 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1672 ms 2424 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20352 KB Output is correct
2 Correct 20 ms 20348 KB Output is correct
3 Correct 21 ms 20352 KB Output is correct
4 Correct 58 ms 21240 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 2424 KB Output is correct
2 Correct 391 ms 2296 KB Output is correct
3 Correct 429 ms 2296 KB Output is correct
4 Correct 406 ms 2424 KB Output is correct
5 Correct 375 ms 2424 KB Output is correct
6 Correct 20 ms 20352 KB Output is correct
7 Correct 19 ms 20352 KB Output is correct
8 Correct 19 ms 20344 KB Output is correct
9 Correct 55 ms 21240 KB Output is correct
10 Correct 10 ms 9984 KB Output is correct
11 Correct 12 ms 9984 KB Output is correct
12 Correct 91 ms 11512 KB Output is correct
13 Correct 11 ms 9856 KB Output is correct
14 Correct 11 ms 9856 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 3 ms 512 KB Output is correct
20 Correct 4 ms 512 KB Output is correct
21 Correct 4 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 65 ms 1500 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 1660 ms 2332 KB Output is correct
28 Correct 3736 ms 85880 KB Output is correct
29 Correct 3949 ms 70740 KB Output is correct
30 Correct 3901 ms 70752 KB Output is correct
31 Correct 3732 ms 86876 KB Output is correct
32 Correct 2 ms 384 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 2432 KB Output is correct
2 Correct 417 ms 2288 KB Output is correct
3 Correct 515 ms 2296 KB Output is correct
4 Correct 415 ms 2344 KB Output is correct
5 Correct 457 ms 2424 KB Output is correct
6 Correct 21 ms 20344 KB Output is correct
7 Correct 20 ms 20352 KB Output is correct
8 Correct 21 ms 20480 KB Output is correct
9 Correct 64 ms 21240 KB Output is correct
10 Correct 10 ms 9856 KB Output is correct
11 Correct 11 ms 9856 KB Output is correct
12 Correct 76 ms 11420 KB Output is correct
13 Correct 10 ms 9900 KB Output is correct
14 Correct 9 ms 9856 KB Output is correct
15 Correct 5556 ms 149840 KB Output is correct
16 Correct 19373 ms 151556 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 69 ms 2936 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 1870 ms 2424 KB Output is correct
30 Correct 3766 ms 89668 KB Output is correct
31 Correct 17982 ms 158324 KB Output is correct
32 Correct 18196 ms 158364 KB Output is correct
33 Correct 4083 ms 74104 KB Output is correct
34 Correct 18293 ms 131040 KB Output is correct
35 Correct 3955 ms 74116 KB Output is correct
36 Correct 18327 ms 130948 KB Output is correct
37 Correct 4046 ms 91408 KB Output is correct
38 Correct 17734 ms 158968 KB Output is correct
39 Correct 2 ms 384 KB Output is correct
40 Correct 18298 ms 131188 KB Output is correct