oj.uz

Submission #225528

# Submission time Handle Problem Language Result Execution time Memory
225528 2020-04-20T19:37:48 Z cgiosy Wombats (IOI13_wombats) C++17
12 / 100
 87 ms 34808 KB 
#pragma GCC optimize("O3")
#pragma GCC target("arch=haswell")
#include "wombats.h"
#include <bits/stdc++.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=8;

int N, M, X[5000][200], Y[5000][200];
int T[K][200][200], L[K], R[K], 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

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 26744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4352 KB Output is correct
2 Correct 6 ms 4352 KB Output is correct
3 Correct 6 ms 4480 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 87 ms 7544 KB Output is correct
12 Correct 7 ms 5024 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 11904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 34808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 11904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 11904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -