oj.uz

Submission #103419

# Submission time Handle Problem Language Result Execution time Memory
103419 2019-03-30T11:35:02 Z andremfq Wombats (IOI13_wombats) C++17
100 / 100
 19946 ms 159208 KB 
//codigo willian
#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 12 ms 9856 KB Output is correct
2 Correct 13 ms 9984 KB Output is correct
3 Correct 120 ms 12744 KB Output is correct
4 Correct 11 ms 9856 KB Output is correct
5 Correct 27 ms 9984 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 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 3 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 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 92 ms 2872 KB Output is correct
12 Correct 3 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 2360 KB Output is correct
2 Correct 346 ms 2296 KB Output is correct
3 Correct 389 ms 2376 KB Output is correct
4 Correct 391 ms 2372 KB Output is correct
5 Correct 524 ms 2296 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
9 Correct 1941 ms 2396 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 24 ms 20488 KB Output is correct
2 Correct 22 ms 20480 KB Output is correct
3 Correct 32 ms 20472 KB Output is correct
4 Correct 61 ms 21880 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 2556 KB Output is correct
2 Correct 359 ms 2424 KB Output is correct
3 Correct 406 ms 2424 KB Output is correct
4 Correct 404 ms 2424 KB Output is correct
5 Correct 440 ms 2424 KB Output is correct
6 Correct 29 ms 20472 KB Output is correct
7 Correct 21 ms 20440 KB Output is correct
8 Correct 25 ms 20480 KB Output is correct
9 Correct 61 ms 21752 KB Output is correct
10 Correct 10 ms 9940 KB Output is correct
11 Correct 12 ms 9984 KB Output is correct
12 Correct 108 ms 12664 KB Output is correct
13 Correct 12 ms 9856 KB Output is correct
14 Correct 11 ms 9856 KB Output is correct
15 Correct 3 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 3 ms 588 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 3 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 77 ms 2808 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 1958 ms 2424 KB Output is correct
28 Correct 3897 ms 89508 KB Output is correct
29 Correct 4160 ms 74024 KB Output is correct
30 Correct 4022 ms 74060 KB Output is correct
31 Correct 4064 ms 91344 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 406 ms 2424 KB Output is correct
2 Correct 397 ms 2296 KB Output is correct
3 Correct 448 ms 2296 KB Output is correct
4 Correct 411 ms 2424 KB Output is correct
5 Correct 474 ms 2424 KB Output is correct
6 Correct 21 ms 20480 KB Output is correct
7 Correct 23 ms 20476 KB Output is correct
8 Correct 23 ms 20584 KB Output is correct
9 Correct 66 ms 21792 KB Output is correct
10 Correct 13 ms 9856 KB Output is correct
11 Correct 13 ms 9984 KB Output is correct
12 Correct 84 ms 12664 KB Output is correct
13 Correct 11 ms 9956 KB Output is correct
14 Correct 13 ms 9976 KB Output is correct
15 Correct 6035 ms 158232 KB Output is correct
16 Correct 19946 ms 159208 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 2 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 2 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 70 ms 2936 KB Output is correct
28 Correct 3 ms 512 KB Output is correct
29 Correct 1977 ms 2380 KB Output is correct
30 Correct 3783 ms 89528 KB Output is correct
31 Correct 17857 ms 154700 KB Output is correct
32 Correct 18746 ms 154664 KB Output is correct
33 Correct 3568 ms 74208 KB Output is correct
34 Correct 18760 ms 127996 KB Output is correct
35 Correct 4037 ms 74148 KB Output is correct
36 Correct 18994 ms 128036 KB Output is correct
37 Correct 4113 ms 90936 KB Output is correct
38 Correct 17835 ms 155516 KB Output is correct
39 Correct 2 ms 384 KB Output is correct
40 Correct 18894 ms 127812 KB Output is correct