Submission #226357

#	Time	Username	Problem	Language	Result	Execution time	Memory
226357		cgiosy	Wombats (IOI13_wombats)	C++17	100 / 100	7737 ms	105308 KiB

wombats

#pragma GCC optimize("O3")
#pragma GCC target("arch=haswell")
#include <bits/stdc++.h>
#include "wombats.h"
#define rep(i,n) for(int i=0; i<n; i++)
#define reset(a) memset(a, 0x3f, sizeof a)
using namespace std;
constexpr int K=20, SZ=512;

int N, M, X[5000][200], Y[5000][200];
int T[SZ][200][200], L[SZ], R[SZ], id=1;
int& mini(int& x, int y) { return x=min(x, y); }
void build(int l, int r, int s=0, int e=N-1, int t=0) {
	auto &D=T[t];
	reset(D);
	if(s==e) {
		rep(i, M) D[i][i]=0;
		rep(y, K) {
			int i=s*K+y;
			rep(j, M) {
				rep(k, M-1) mini(D[j][k+1], D[j][k]+X[i][k]);
				rep(k, M-1) mini(D[j][M-k-2], D[j][M-k-1]+X[i][M-k-2]);
				rep(k, M) D[j][k]+=Y[i][k];
			}
		}
		return;
	}

	int m=s+e>>1;
	if(l<=m) build(l, r, s, m, L[t]=L[t] ?: id++);
	if(r>m) build(l, r, m+1, e, R[t]=R[t] ?: id++);

	auto &A=T[L[t]], &B=T[R[t]];
	rep(a, M) rep(i, M) rep(b, M)
		D[a][b]=min(D[a][b], A[a][i]+B[i][b]);
}
void init(int P, int Q, int H[5000][200], int V[5000][200]) {
	N=(P+K-1)/K, M=Q;
	reset(X);
	rep(i, P) rep(j, Q-1) X[i][j]=H[i][j];
	rep(i, P-1) rep(j, Q) Y[i][j]=V[i][j];
	build(0, N-1);
}
void changeH(int p, int q, int w) { X[p][q]=w; build(p/K, p/K); }
void changeV(int p, int q, int w) { Y[p][q]=w; build(p/K, p/K); }
int escape(int a, int b) { return T[0][a][b]; }

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;
      ^~~
wombats.cpp: In function 'void build(int, int, int, int, int)':
wombats.cpp:29:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=s+e>>1;
        ~^~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24