oj.uz

Submission #425380

# Submission time Handle Problem Language Result Execution time Memory
425380 2021-06-13T00:59:18 Z frodakcin Wombats (IOI13_wombats) C++17
100 / 100
 6198 ms 112020 KB 
#include "wombats.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}
bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}

const int MR = 5e3+10;
const int SM = 20;
const int MC = 2e2+10;

int R, C, B, H[5000][200], V[5000][200], st[1024][MC][MC], dp[MC], best[MC];
bool cur;

void compute_block(int n, int l, int r)
{
	for(int i=0;i<C;++i)
	{
		memset(dp, 0x3f, C*sizeof*dp);
		dp[i]=0;
		for(int j=l;j<r;++j)
		{
			for(int c=0;c+1<C;++c)
				ckmin(dp[c+1], dp[c]+H[j][c]);
			for(int c=C-1;c>0;--c)
				ckmin(dp[c-1], dp[c]+H[j][c-1]);
			if(j+1<R)
				for(int c=0;c<C;++c)
					dp[c] += V[j][c];
		}
		memcpy(st[n][i], dp, C*sizeof*dp);
	}
}

void merge(int x, int y, int z)
{
	memset(st[z], 0x3f, sizeof st[z]);
	memset(best, 0, C*sizeof*best);
	best[C]=C-1;
	/*
	for(int i=0;i<C;++i) for(int j=0;j<C;++j) for(int k=0;k<C;++k)
		ckmin(st[z][i][j], st[x][i][k]+st[y][k][j]);
		*/
	for(int d=-C+1;d<C;++d)
		for(int i=std::max(0, -d), mi=(C-std::max(0, d));i<mi;++i)
		{
			int j=i+d;
			int tr=-1;
			for(int k=best[i];k<=best[i+1];++k)
				if(ckmin(st[z][i][j], st[x][i][k]+st[y][k][j]))
					tr=k;
			best[i]=tr;
		}
}

void upd(int n, int l, int r, int q)
{
	if(r-l<=SM)
		compute_block(n, l, r);
	else
	{
		int m=l+(r-l)/2;
		if(q==-1 || q<m) upd(n<<1, l, m, q);
		if(q==-1 || m<=q) upd(n<<1|1, m, r, q);
		merge(n<<1, n<<1|1, n);
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
	::R=R;
	::C=C;
	memcpy(::H, H, sizeof ::H);
	memcpy(::V, V, sizeof ::V);
	upd(1, 0, R, -1);
}

void changeH(int P, int Q, int W) { // 500x tot
	H[P][Q]=W;
	upd(1, 0, R, P);
}

void changeV(int P, int Q, int W) { // 500x tot
	V[P][Q]=W;
	upd(1, 0, R, P);
}

int escape(int V1, int V2) { // 200000x
	//return mat[0][V1][V2];
	return st[1][V1][V2];
}

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;
      |      ^~~
wombats.cpp:7:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    7 | bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}
      |            ^~~~
wombats.cpp:7:27: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    7 | bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}
      |                           ^~~~
wombats.cpp:8:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
      |            ^~~~
wombats.cpp:8:27: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
      |                           ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 57140 KB Output is correct
2 Correct 63 ms 57072 KB Output is correct
3 Correct 157 ms 58676 KB Output is correct
4 Correct 105 ms 57140 KB Output is correct
5 Correct 68 ms 57144 KB Output is correct
6 Correct 5 ms 8140 KB Output is correct
7 Correct 6 ms 8012 KB Output is correct
8 Correct 8 ms 8012 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 5 ms 8012 KB Output is correct
3 Correct 5 ms 8080 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 6 ms 8272 KB Output is correct
6 Correct 6 ms 8180 KB Output is correct
7 Correct 7 ms 8140 KB Output is correct
8 Correct 6 ms 8140 KB Output is correct
9 Correct 6 ms 8140 KB Output is correct
10 Correct 7 ms 8140 KB Output is correct
11 Correct 103 ms 9216 KB Output is correct
12 Correct 6 ms 8140 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 10156 KB Output is correct
2 Correct 100 ms 10152 KB Output is correct
3 Correct 137 ms 10076 KB Output is correct
4 Correct 135 ms 10176 KB Output is correct
5 Correct 133 ms 10160 KB Output is correct
6 Correct 6 ms 8112 KB Output is correct
7 Correct 5 ms 8012 KB Output is correct
8 Correct 5 ms 8140 KB Output is correct
9 Correct 485 ms 10168 KB Output is correct
10 Correct 6 ms 8140 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 61216 KB Output is correct
2 Correct 73 ms 61256 KB Output is correct
3 Correct 110 ms 61256 KB Output is correct
4 Correct 123 ms 62048 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 10048 KB Output is correct
2 Correct 100 ms 10060 KB Output is correct
3 Correct 135 ms 10184 KB Output is correct
4 Correct 132 ms 10176 KB Output is correct
5 Correct 132 ms 10060 KB Output is correct
6 Correct 84 ms 61168 KB Output is correct
7 Correct 63 ms 61260 KB Output is correct
8 Correct 94 ms 61260 KB Output is correct
9 Correct 134 ms 61964 KB Output is correct
10 Correct 70 ms 57048 KB Output is correct
11 Correct 60 ms 57140 KB Output is correct
12 Correct 139 ms 58684 KB Output is correct
13 Correct 80 ms 57144 KB Output is correct
14 Correct 62 ms 57156 KB Output is correct
15 Correct 5 ms 8012 KB Output is correct
16 Correct 5 ms 8140 KB Output is correct
17 Correct 5 ms 8140 KB Output is correct
18 Correct 6 ms 8140 KB Output is correct
19 Correct 5 ms 8076 KB Output is correct
20 Correct 5 ms 8104 KB Output is correct
21 Correct 6 ms 8140 KB Output is correct
22 Correct 7 ms 8172 KB Output is correct
23 Correct 7 ms 8140 KB Output is correct
24 Correct 6 ms 8140 KB Output is correct
25 Correct 81 ms 9084 KB Output is correct
26 Correct 6 ms 8108 KB Output is correct
27 Correct 511 ms 10168 KB Output is correct
28 Correct 1441 ms 82432 KB Output is correct
29 Correct 1478 ms 84392 KB Output is correct
30 Correct 1455 ms 84612 KB Output is correct
31 Correct 1585 ms 87872 KB Output is correct
32 Correct 5 ms 8140 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 10156 KB Output is correct
2 Correct 99 ms 10120 KB Output is correct
3 Correct 134 ms 10172 KB Output is correct
4 Correct 143 ms 10164 KB Output is correct
5 Correct 129 ms 10060 KB Output is correct
6 Correct 86 ms 61276 KB Output is correct
7 Correct 63 ms 61148 KB Output is correct
8 Correct 83 ms 61260 KB Output is correct
9 Correct 117 ms 62136 KB Output is correct
10 Correct 64 ms 57036 KB Output is correct
11 Correct 81 ms 57036 KB Output is correct
12 Correct 168 ms 58724 KB Output is correct
13 Correct 82 ms 57140 KB Output is correct
14 Correct 76 ms 57036 KB Output is correct
15 Correct 977 ms 102968 KB Output is correct
16 Correct 6198 ms 105972 KB Output is correct
17 Correct 6 ms 8140 KB Output is correct
18 Correct 5 ms 8132 KB Output is correct
19 Correct 6 ms 8120 KB Output is correct
20 Correct 6 ms 8140 KB Output is correct
21 Correct 6 ms 8140 KB Output is correct
22 Correct 7 ms 8104 KB Output is correct
23 Correct 7 ms 8140 KB Output is correct
24 Correct 7 ms 8140 KB Output is correct
25 Correct 7 ms 8140 KB Output is correct
26 Correct 7 ms 8140 KB Output is correct
27 Correct 106 ms 10424 KB Output is correct
28 Correct 6 ms 8140 KB Output is correct
29 Correct 507 ms 10228 KB Output is correct
30 Correct 1428 ms 86072 KB Output is correct
31 Correct 4937 ms 111316 KB Output is correct
32 Correct 4975 ms 111420 KB Output is correct
33 Correct 1479 ms 84468 KB Output is correct
34 Correct 5323 ms 109452 KB Output is correct
35 Correct 1437 ms 84364 KB Output is correct
36 Correct 4994 ms 109408 KB Output is correct
37 Correct 1592 ms 87804 KB Output is correct
38 Correct 5301 ms 112020 KB Output is correct
39 Correct 6 ms 8140 KB Output is correct
40 Correct 5212 ms 109744 KB Output is correct