oj.uz

Submission #764156

# Submission time Handle Problem Language Result Execution time Memory
764156 2023-06-23T07:54:18 Z ymm Wombats (IOI13_wombats) C++17
76 / 100
 19047 ms 21200 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;
int r;
const int C = 100;
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];

#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 recalc()
{
	Loop (i,0,C) {
		Loop (x,0,C/vs) Loop (y,0,vs)
			ans[i][x][y] = 1e6;
		ans[i][i % (C/vs)][i / (C/vs)] = 0;
	}
	Loop (i,0,r-1) {
		Loop (p,0,C) {
			to_right(ans[p], i);
			to_left(ans[p], i);
		}
		Loop (p,0,C)
			down(ans[p], i);
	}
	Loop (p,0,C) {
		to_left(ans[p], r-1);
		to_right(ans[p], r-1);
	}
}

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);
	recalc();
}

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

void changeV(int P, int Q, int W) {
	V[P][Q % (C/vs)][Q / (C/vs)] = W;
	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 18745 ms 15992 KB Output is correct
2 Correct 18902 ms 15988 KB Output is correct
3 Correct 18999 ms 17520 KB Output is correct
4 Correct 19047 ms 15980 KB Output is correct
5 Correct 18790 ms 15980 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 53 ms 1436 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 764 KB Output is correct
2 Correct 75 ms 752 KB Output is correct
3 Correct 76 ms 752 KB Output is correct
4 Correct 76 ms 756 KB Output is correct
5 Correct 76 ms 748 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 374 ms 748 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18899 ms 19892 KB Output is correct
2 Correct 18734 ms 19896 KB Output is correct
3 Correct 18663 ms 19900 KB Output is correct
4 Correct 18579 ms 20888 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 764 KB Output is correct
2 Correct 75 ms 748 KB Output is correct
3 Correct 76 ms 752 KB Output is correct
4 Correct 76 ms 724 KB Output is correct
5 Correct 76 ms 764 KB Output is correct
6 Correct 18535 ms 19900 KB Output is correct
7 Correct 18533 ms 19888 KB Output is correct
8 Correct 18559 ms 19900 KB Output is correct
9 Correct 18502 ms 20680 KB Output is correct
10 Correct 18619 ms 15980 KB Output is correct
11 Correct 18631 ms 15984 KB Output is correct
12 Correct 18638 ms 17520 KB Output is correct
13 Correct 18577 ms 15984 KB Output is correct
14 Correct 18600 ms 15984 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 53 ms 1344 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 368 ms 748 KB Output is correct
28 Correct 18520 ms 20424 KB Output is correct
29 Correct 15155 ms 16780 KB Output is correct
30 Correct 15192 ms 16940 KB Output is correct
31 Correct 18623 ms 21200 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 852 KB Output is correct
2 Correct 75 ms 748 KB Output is correct
3 Correct 76 ms 724 KB Output is correct
4 Correct 76 ms 756 KB Output is correct
5 Correct 76 ms 748 KB Output is correct
6 Correct 18570 ms 19896 KB Output is correct
7 Correct 18532 ms 19896 KB Output is correct
8 Correct 18680 ms 19892 KB Output is correct
9 Correct 18590 ms 20768 KB Output is correct
10 Correct 18502 ms 15980 KB Output is correct
11 Correct 18541 ms 15980 KB Output is correct
12 Correct 18514 ms 17520 KB Output is correct
13 Correct 18477 ms 15980 KB Output is correct
14 Correct 18517 ms 15984 KB Output is correct
15 Incorrect 326 ms 19784 KB Output isn't correct
16 Halted 0 ms 0 KB -