oj.uz

Submission #764228

# Submission time Handle Problem Language Result Execution time Memory
764228 2023-06-23T09:01:38 Z ymm Wombats (IOI13_wombats) C++17
100 / 100
 6432 ms 44144 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("avx2")

const int R = 5000;
const int S = 500;
int r;
const int C = 200;
const int Q = 500;
const int vs = 8;
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))

int i2v(int x) { return x % (C/vs) * vs + x / (C/vs); }

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][i2v(i)][x][y] = 1e6;
		pans[s][i2v(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[i2v(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 5930 ms 37712 KB Output is correct
2 Correct 5948 ms 37712 KB Output is correct
3 Correct 6018 ms 39328 KB Output is correct
4 Correct 6069 ms 37716 KB Output is correct
5 Correct 5956 ms 37720 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 0 ms 596 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 1 ms 724 KB Output is correct
11 Correct 53 ms 1724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 1364 KB Output is correct
2 Correct 166 ms 1364 KB Output is correct
3 Correct 167 ms 1364 KB Output is correct
4 Correct 175 ms 1432 KB Output is correct
5 Correct 167 ms 1364 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 885 ms 1428 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5897 ms 41716 KB Output is correct
2 Correct 5959 ms 41628 KB Output is correct
3 Correct 5945 ms 41632 KB Output is correct
4 Correct 5963 ms 42304 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 1424 KB Output is correct
2 Correct 165 ms 1364 KB Output is correct
3 Correct 167 ms 1440 KB Output is correct
4 Correct 168 ms 1364 KB Output is correct
5 Correct 167 ms 1424 KB Output is correct
6 Correct 5865 ms 41624 KB Output is correct
7 Correct 5986 ms 41628 KB Output is correct
8 Correct 5944 ms 41548 KB Output is correct
9 Correct 6041 ms 42308 KB Output is correct
10 Correct 5943 ms 37636 KB Output is correct
11 Correct 5906 ms 37704 KB Output is correct
12 Correct 6070 ms 39252 KB Output is correct
13 Correct 6105 ms 37716 KB Output is correct
14 Correct 6055 ms 37716 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 564 KB Output is correct
18 Correct 1 ms 828 KB Output is correct
19 Correct 1 ms 700 KB Output is correct
20 Correct 2 ms 724 KB Output is correct
21 Correct 1 ms 724 KB Output is correct
22 Correct 2 ms 752 KB Output is correct
23 Correct 1 ms 724 KB Output is correct
24 Correct 1 ms 700 KB Output is correct
25 Correct 53 ms 2052 KB Output is correct
26 Correct 1 ms 696 KB Output is correct
27 Correct 837 ms 1612 KB Output is correct
28 Correct 6383 ms 42208 KB Output is correct
29 Correct 5857 ms 35128 KB Output is correct
30 Correct 5445 ms 35236 KB Output is correct
31 Correct 6115 ms 43532 KB Output is correct
32 Correct 1 ms 596 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 1492 KB Output is correct
2 Correct 173 ms 1492 KB Output is correct
3 Correct 167 ms 1504 KB Output is correct
4 Correct 167 ms 1504 KB Output is correct
5 Correct 169 ms 1492 KB Output is correct
6 Correct 5974 ms 41620 KB Output is correct
7 Correct 5902 ms 41620 KB Output is correct
8 Correct 5974 ms 41624 KB Output is correct
9 Correct 5909 ms 42372 KB Output is correct
10 Correct 5959 ms 37716 KB Output is correct
11 Correct 6214 ms 37716 KB Output is correct
12 Correct 6171 ms 39248 KB Output is correct
13 Correct 6030 ms 37712 KB Output is correct
14 Correct 5925 ms 37744 KB Output is correct
15 Correct 280 ms 42060 KB Output is correct
16 Correct 6176 ms 44144 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 1 ms 824 KB Output is correct
24 Correct 2 ms 696 KB Output is correct
25 Correct 2 ms 724 KB Output is correct
26 Correct 1 ms 828 KB Output is correct
27 Correct 54 ms 2368 KB Output is correct
28 Correct 1 ms 724 KB Output is correct
29 Correct 831 ms 1504 KB Output is correct
30 Correct 6123 ms 42612 KB Output is correct
31 Correct 6189 ms 42928 KB Output is correct
32 Correct 6312 ms 42952 KB Output is correct
33 Correct 5798 ms 35464 KB Output is correct
34 Correct 5868 ms 35736 KB Output is correct
35 Correct 5452 ms 35276 KB Output is correct
36 Correct 5556 ms 35876 KB Output is correct
37 Correct 6143 ms 43628 KB Output is correct
38 Correct 6432 ms 43752 KB Output is correct
39 Correct 1 ms 596 KB Output is correct
40 Correct 6167 ms 35772 KB Output is correct