oj.uz

Submission #764219

# Submission time Handle Problem Language Result Execution time Memory
764219 2023-06-23T08:48:44 Z ymm Wombats (IOI13_wombats) C++17
100 / 100
 15415 ms 41664 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))

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 15169 ms 28800 KB Output is correct
2 Correct 15283 ms 28808 KB Output is correct
3 Correct 15236 ms 30448 KB Output is correct
4 Correct 15165 ms 28808 KB Output is correct
5 Correct 15074 ms 28808 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 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 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 2 ms 724 KB Output is correct
8 Correct 1 ms 692 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 54 ms 1856 KB Output is correct
12 Correct 1 ms 696 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 1344 KB Output is correct
2 Correct 271 ms 1328 KB Output is correct
3 Correct 272 ms 1344 KB Output is correct
4 Correct 278 ms 1344 KB Output is correct
5 Correct 279 ms 1344 KB Output is correct
6 Correct 1 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 1401 ms 1356 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 15008 ms 32760 KB Output is correct
2 Correct 15088 ms 32744 KB Output is correct
3 Correct 15108 ms 32764 KB Output is correct
4 Correct 15060 ms 33608 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 1348 KB Output is correct
2 Correct 309 ms 1328 KB Output is correct
3 Correct 274 ms 1348 KB Output is correct
4 Correct 272 ms 1480 KB Output is correct
5 Correct 273 ms 1364 KB Output is correct
6 Correct 15008 ms 32756 KB Output is correct
7 Correct 14920 ms 32872 KB Output is correct
8 Correct 14923 ms 32764 KB Output is correct
9 Correct 15153 ms 33600 KB Output is correct
10 Correct 14828 ms 28796 KB Output is correct
11 Correct 14858 ms 28924 KB Output is correct
12 Correct 14924 ms 30492 KB Output is correct
13 Correct 14899 ms 28808 KB Output is correct
14 Correct 14811 ms 28860 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 560 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 2 ms 768 KB Output is correct
22 Correct 1 ms 724 KB Output is correct
23 Correct 1 ms 724 KB Output is correct
24 Correct 1 ms 724 KB Output is correct
25 Correct 54 ms 1836 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 1343 ms 1360 KB Output is correct
28 Correct 14938 ms 33152 KB Output is correct
29 Correct 14955 ms 27744 KB Output is correct
30 Correct 13572 ms 27492 KB Output is correct
31 Correct 14934 ms 34288 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 275 ms 1336 KB Output is correct
2 Correct 269 ms 1236 KB Output is correct
3 Correct 276 ms 1364 KB Output is correct
4 Correct 273 ms 1364 KB Output is correct
5 Correct 274 ms 1364 KB Output is correct
6 Correct 15244 ms 32820 KB Output is correct
7 Correct 15415 ms 32744 KB Output is correct
8 Correct 15072 ms 32764 KB Output is correct
9 Correct 14962 ms 33572 KB Output is correct
10 Correct 14859 ms 28800 KB Output is correct
11 Correct 14812 ms 28788 KB Output is correct
12 Correct 14896 ms 30492 KB Output is correct
13 Correct 14929 ms 28760 KB Output is correct
14 Correct 14930 ms 28804 KB Output is correct
15 Correct 391 ms 32784 KB Output is correct
16 Correct 15103 ms 35612 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 1 ms 692 KB Output is correct
22 Correct 1 ms 696 KB Output is correct
23 Correct 1 ms 724 KB Output is correct
24 Correct 1 ms 724 KB Output is correct
25 Correct 1 ms 756 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 54 ms 3144 KB Output is correct
28 Correct 1 ms 724 KB Output is correct
29 Correct 1346 ms 1344 KB Output is correct
30 Correct 14885 ms 36876 KB Output is correct
31 Correct 14951 ms 41048 KB Output is correct
32 Correct 15036 ms 41076 KB Output is correct
33 Correct 14797 ms 30892 KB Output is correct
34 Correct 14930 ms 34928 KB Output is correct
35 Correct 13593 ms 31012 KB Output is correct
36 Correct 13748 ms 35156 KB Output is correct
37 Correct 14965 ms 38460 KB Output is correct
38 Correct 14979 ms 41664 KB Output is correct
39 Correct 1 ms 596 KB Output is correct
40 Correct 14904 ms 34908 KB Output is correct