oj.uz

Submission #764189

# Submission time Handle Problem Language Result Execution time Memory
764189 2023-06-23T08:27:22 Z ymm Wombats (IOI13_wombats) C++17
37 / 100
 15548 ms 32816 KB 
#include "wombats.h"

#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
#define LoopR(x, l, r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll ,ll > pll;
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")

const int R = 5000;
const int S = 1000;
int r;
const int C = 200;
const int Q = 500;
const int vs = 4;
typedef int vec __attribute__((vector_size(4*vs), aligned(4*vs)));

vec H[R][C/vs], V[R][C];
vec PS[R][C/vs];
vec ans[C][C/vs];

vec pans[R/S][C][C/vs];

#define MIN(x, y) ((x)<(y)?(x):(y))

void to_right(vec *ans, int p)
{
	Loop (i,0,C/vs-1)
		ans[i+1] = MIN(ans[i+1], ans[i] + H[p][i]);
	int mn = 1e9;
	vec x;
	x[0] = mn;
	Loop (i,0,vs-1) {
		mn = MIN(mn, ans[C/vs-1][i] - PS[p][C/vs-1][i]);
		x[i+1] = mn;
	}
	Loop (i,0,C/vs)
		ans[i] = MIN(ans[i], x + PS[p][i]); 
}

void to_left(vec *ans, int p)
{
	LoopR (i,0,C/vs-1)
		ans[i] = MIN(ans[i], ans[i+1] + H[p][i]);
	int mn = 1e9;
	vec x;
	x[vs-1] = mn;
	LoopR (i,0,vs-1) {
		mn = MIN(mn, ans[0][i+1] + PS[p][0][i+1]);
		x[i] = mn;
	}
	LoopR (i,0,C/vs)
		ans[i] = MIN(ans[i], x - PS[p][i]);
}

void down(vec *ans, int p)
{
	Loop (i,0,C/vs)
		ans[i] += V[p][i];
}

void recalcp(int s)
{
	int sl = s*S, sr = min(s*S+S, r);
	Loop (i,0,C) {
		Loop (x,0,C/vs) Loop (y,0,vs)
			pans[s][i][x][y] = 1e6;
		pans[s][i][i % (C/vs)][i / (C/vs)] = 0;
	}
	Loop (i,sl,sr) {
		Loop (p,0,C) {
			to_right(pans[s][p], i);
			to_left(pans[s][p], i);
		}
		if (i < r-1) {
			Loop (p,0,C)
				down(pans[s][p], i);
		}
	}
}

void recalc()
{
	memcpy(ans, pans[0], sizeof(ans));
	static int tmp[C][C];
	int (*a)[C] = (int (*)[C])(void *)ans;
	for (int s = 1; s*S < r; ++s) {
		int (*b)[C] = (int (*)[C])(void *)pans[s];
		Loop (i,0,C) Loop (j,0,C)
			tmp[i][j] = a[i][0] + b[0][j];
		Loop (i,0,C) Loop (j,1,C) Loop (k,0,C)
			tmp[i][k] = MIN(tmp[i][k], a[i][j] + b[j][k]);
		memcpy(ans, tmp, sizeof(ans));
	}
}

void recalc_ps(int p)
{
	Loop (i,0,vs)
		PS[p][0][i] = 0;
	Loop (i,0,C/vs-1)
		PS[p][i+1] = PS[p][i] + H[p][i];
	vec x = {};
	Loop (i,0,vs-1)
		x[i+1] = x[i] + PS[p][C/vs-1][i] + H[p][C/vs-1][i];
	Loop (i,0,C/vs)
		PS[p][i] += x;
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
	::r = r;
	Loop (i,0,r) Loop (j,0,C-1) {
		int x = j < c-1? h[i][j]: 1001;
		H[i][j % (C/vs)][j / (C/vs)] = x;
	}
	Loop (i,0,r-1) Loop (j,0,C) {
		int x = j < c? v[i][j]: 1001;
		V[i][j % (C/vs)][j / (C/vs)] = x;
	}
	Loop (i,0,r)
		recalc_ps(i);
	for (int i = 0; i*S < r; ++i)
		recalcp(i);
	recalc();
}

void changeH(int P, int Q, int W) {
	H[P][Q % (C/vs)][Q / (C/vs)] = W;
	recalc_ps(P);
	recalcp(P/S);
	recalc();
}

void changeV(int P, int Q, int W) {
	V[P][Q % (C/vs)][Q / (C/vs)] = W;
	recalcp(P/S);
	recalc();
}

int escape(int V1, int V2) {
	return ans[V1][V2 % (C/vs)][V2 / (C/vs)];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15281 ms 28780 KB Output is correct
2 Correct 15338 ms 28772 KB Output is correct
3 Correct 15252 ms 30312 KB Output is correct
4 Correct 15185 ms 28780 KB Output is correct
5 Correct 15268 ms 28784 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 0 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 72 ms 1748 KB Output is correct
12 Correct 2 ms 724 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 1260 KB Output is correct
2 Correct 271 ms 1276 KB Output is correct
3 Correct 286 ms 1284 KB Output is correct
4 Correct 343 ms 1280 KB Output is correct
5 Correct 279 ms 1268 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1454 ms 1284 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15539 ms 32684 KB Output is correct
2 Incorrect 15140 ms 32688 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 1236 KB Output is correct
2 Correct 294 ms 1280 KB Output is correct
3 Correct 284 ms 1264 KB Output is correct
4 Correct 283 ms 1268 KB Output is correct
5 Correct 285 ms 1272 KB Output is correct
6 Correct 14945 ms 32688 KB Output is correct
7 Incorrect 15548 ms 32696 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 1264 KB Output is correct
2 Correct 293 ms 1276 KB Output is correct
3 Correct 282 ms 1268 KB Output is correct
4 Correct 274 ms 1268 KB Output is correct
5 Correct 274 ms 1272 KB Output is correct
6 Correct 15287 ms 32684 KB Output is correct
7 Incorrect 15036 ms 32816 KB Output isn't correct
8 Halted 0 ms 0 KB -