oj.uz

Submission #764226

# Submission time Handle Problem Language Result Execution time Memory
764226 2023-06-23T09:00:06 Z ymm Wombats (IOI13_wombats) C++17
100 / 100
 9841 ms 42416 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 = 1000;
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 9060 ms 36928 KB Output is correct
2 Correct 9095 ms 36928 KB Output is correct
3 Correct 9109 ms 38524 KB Output is correct
4 Correct 9107 ms 36932 KB Output is correct
5 Correct 9070 ms 36932 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 660 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 1740 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 167 ms 1420 KB Output is correct
2 Correct 165 ms 1364 KB Output is correct
3 Correct 171 ms 1444 KB Output is correct
4 Correct 168 ms 1364 KB Output is correct
5 Correct 180 ms 1440 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 0 ms 596 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 855 ms 1364 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 9075 ms 40840 KB Output is correct
2 Correct 9184 ms 40844 KB Output is correct
3 Correct 9307 ms 40848 KB Output is correct
4 Correct 9168 ms 41636 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 1420 KB Output is correct
2 Correct 167 ms 1364 KB Output is correct
3 Correct 172 ms 1364 KB Output is correct
4 Correct 167 ms 1424 KB Output is correct
5 Correct 168 ms 1428 KB Output is correct
6 Correct 9195 ms 40840 KB Output is correct
7 Correct 9152 ms 40860 KB Output is correct
8 Correct 9237 ms 40840 KB Output is correct
9 Correct 9287 ms 41640 KB Output is correct
10 Correct 9293 ms 36932 KB Output is correct
11 Correct 9154 ms 36924 KB Output is correct
12 Correct 9194 ms 38496 KB Output is correct
13 Correct 9232 ms 36936 KB Output is correct
14 Correct 9179 ms 36928 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 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 1 ms 724 KB Output is correct
22 Correct 2 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 53 ms 1684 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 833 ms 1424 KB Output is correct
28 Correct 9134 ms 41128 KB Output is correct
29 Correct 9182 ms 34076 KB Output is correct
30 Correct 8565 ms 34088 KB Output is correct
31 Correct 9503 ms 42240 KB Output is correct
32 Correct 1 ms 640 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 1504 KB Output is correct
2 Correct 165 ms 1492 KB Output is correct
3 Correct 173 ms 1508 KB Output is correct
4 Correct 168 ms 1516 KB Output is correct
5 Correct 180 ms 1508 KB Output is correct
6 Correct 9236 ms 40912 KB Output is correct
7 Correct 9092 ms 40896 KB Output is correct
8 Correct 9147 ms 41032 KB Output is correct
9 Correct 9164 ms 42092 KB Output is correct
10 Correct 9104 ms 36952 KB Output is correct
11 Correct 9138 ms 36964 KB Output is correct
12 Correct 9471 ms 39024 KB Output is correct
13 Correct 9294 ms 36968 KB Output is correct
14 Correct 9183 ms 37052 KB Output is correct
15 Correct 327 ms 40836 KB Output is correct
16 Correct 9841 ms 42416 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 0 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 724 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 1 ms 724 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 79 ms 1688 KB Output is correct
28 Correct 1 ms 724 KB Output is correct
29 Correct 844 ms 1444 KB Output is correct
30 Correct 9690 ms 41184 KB Output is correct
31 Correct 9345 ms 41532 KB Output is correct
32 Correct 9301 ms 41724 KB Output is correct
33 Correct 9201 ms 34004 KB Output is correct
34 Correct 9670 ms 34404 KB Output is correct
35 Correct 8574 ms 34052 KB Output is correct
36 Correct 8576 ms 34508 KB Output is correct
37 Correct 9165 ms 42176 KB Output is correct
38 Correct 9274 ms 42168 KB Output is correct
39 Correct 1 ms 596 KB Output is correct
40 Correct 9195 ms 34432 KB Output is correct