oj.uz

Submission #226356

# Submission time Handle Problem Language Result Execution time Memory
226356 2020-04-23T12:40:42 Z cgiosy Wombats (IOI13_wombats) C++17
18 / 100
 7292 ms 95864 KB 
#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=504;
 
int X[5000][200], Y[5000][200], N, M;
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=249, int t=0) {
	auto &D=T[t];
	reset(D);
	if(s==e) {
		rep(i, 200) D[i][i]=0;
		rep(y, K) {
			int i=s*K+y;
			rep(j, 200) {
				rep(k, 199) mini(D[j][k+1], D[j][k]+X[i][k]);
				rep(k, 199) mini(D[j][198-k], D[j][199-k]+X[i][198-k]);
				rep(k, 200) 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, 200) rep(i, 200) rep(b, 200)
		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 Correct 7147 ms 90304 KB Output is correct
2 Correct 7199 ms 90448 KB Output is correct
3 Correct 7272 ms 93124 KB Output is correct
4 Correct 7097 ms 90232 KB Output is correct
5 Correct 7226 ms 90300 KB Output is correct
6 Incorrect 20 ms 5632 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 5632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1291 ms 7036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7214 ms 94232 KB Output is correct
2 Correct 7240 ms 94328 KB Output is correct
3 Correct 7221 ms 94352 KB Output is correct
4 Correct 7292 ms 95864 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1271 ms 7160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1286 ms 7160 KB Output isn't correct
2 Halted 0 ms 0 KB -