oj.uz

Submission #103056

# Submission time Handle Problem Language Result Execution time Memory
103056 2019-03-29T00:54:57 Z wilwxk Wombats (IOI13_wombats) C++11
76 / 100
 20000 ms 134088 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

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

int seg[TAM][MAXC][MAXC];
int ps[MAXR][MAXC];
int bini[TAM], bfim[TAM];
short v[MAXR][MAXC], h[MAXR][MAXC];
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 11 ms 9344 KB Output is correct
2 Correct 11 ms 9344 KB Output is correct
3 Correct 75 ms 11968 KB Output is correct
4 Correct 10 ms 9344 KB Output is correct
5 Correct 12 ms 9344 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 2 ms 384 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 91 ms 2928 KB Output is correct
12 Correct 4 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 2168 KB Output is correct
2 Correct 427 ms 2020 KB Output is correct
3 Correct 483 ms 2044 KB Output is correct
4 Correct 586 ms 2040 KB Output is correct
5 Correct 460 ms 2040 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 2078 ms 2068 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 23 ms 19712 KB Output is correct
2 Correct 23 ms 19684 KB Output is correct
3 Correct 23 ms 19712 KB Output is correct
4 Correct 70 ms 21112 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 2140 KB Output is correct
2 Correct 444 ms 2040 KB Output is correct
3 Correct 394 ms 2040 KB Output is correct
4 Correct 454 ms 2168 KB Output is correct
5 Correct 446 ms 2168 KB Output is correct
6 Correct 21 ms 19788 KB Output is correct
7 Correct 22 ms 19712 KB Output is correct
8 Correct 22 ms 19712 KB Output is correct
9 Correct 84 ms 20984 KB Output is correct
10 Correct 10 ms 9216 KB Output is correct
11 Correct 12 ms 9344 KB Output is correct
12 Correct 71 ms 12024 KB Output is correct
13 Correct 14 ms 9216 KB Output is correct
14 Correct 10 ms 9216 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 2 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 4 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 74 ms 2808 KB Output is correct
26 Correct 3 ms 640 KB Output is correct
27 Correct 1976 ms 2040 KB Output is correct
28 Correct 4013 ms 75924 KB Output is correct
29 Correct 4059 ms 62668 KB Output is correct
30 Correct 4487 ms 62752 KB Output is correct
31 Correct 4234 ms 77732 KB Output is correct
32 Correct 2 ms 384 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 1912 KB Output is correct
2 Correct 432 ms 2020 KB Output is correct
3 Correct 474 ms 2056 KB Output is correct
4 Correct 499 ms 2168 KB Output is correct
5 Correct 483 ms 2168 KB Output is correct
6 Correct 22 ms 19712 KB Output is correct
7 Correct 23 ms 19712 KB Output is correct
8 Correct 20 ms 19712 KB Output is correct
9 Correct 61 ms 21084 KB Output is correct
10 Correct 12 ms 9216 KB Output is correct
11 Correct 11 ms 9216 KB Output is correct
12 Correct 83 ms 12040 KB Output is correct
13 Correct 10 ms 9216 KB Output is correct
14 Correct 12 ms 9216 KB Output is correct
15 Correct 5447 ms 132600 KB Output is correct
16 Execution timed out 20043 ms 134088 KB Time limit exceeded
17 Halted 0 ms 0 KB -