oj.uz

Submission #480321

# Submission time Handle Problem Language Result Execution time Memory
480321 2021-10-15T16:19:51 Z AdamGS Wombats (IOI13_wombats) C++14
100 / 100
 16625 ms 189112 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int MAXN=5e3+7, MAXM=207, N=1<<9, INF=1e9+7;
int tr[2*N][200][200];
int A[10*N+1][MAXM], B[10*N+1][MAXM], n, m;
void liczlisc(int x) {
	int dwa[10][m][m];
	rep(i, 10) {
		int pref[m][2];
		pref[0][0]=pref[0][1]=2;
		rep(j, m-1) {
			pref[j+1][0]=pref[j][0]+A[10*x+i][j];
			pref[j+1][1]=pref[j][1]+A[10*x+i+1][j];
		}
		int lst[m+2], lst2[m+2];
		lst[0]=lst2[0]=0;
		lst[1]=lst2[1]=m-1;
		for(int r=m-1; r>=0; --r) {
			int akt[m+2], akt2[m+2];
			akt[0]=akt2[0]=0;
			akt[m-r+1]=akt2[m-r+1]=m-1;
			rep(p, m-r) {
				int k=p+r;
				pair<int,int>mi={INF, INF};
				for(int l=lst[p]; l<=lst[p+1]; ++l) {
					mi=min(mi, {abs(pref[l][0]-pref[p][0])+abs(pref[k][1]-pref[l][1])+B[10*x+i][l], l});
				}
				akt[p+1]=mi.nd;
				dwa[i][p][k]=mi.st;
				mi={INF, INF};
				for(int l=lst2[p]; l<=lst2[p+1]; ++l) {
					mi=min(mi, {abs(pref[k][0]-pref[l][0])+abs(pref[l][1]-pref[p][1])+B[10*x+i][l], l});
				}
				akt2[p+1]=mi.nd;
				dwa[i][k][p]=mi.st;
			}
			rep(p, m-r+2) {
				lst[p]=akt[p];
				lst2[p]=akt2[p];
			}
		}
	}
	rep(i, m) rep(j, m) tr[N+x][i][j]=dwa[0][i][j];
	rep(i, 9) {
		int tmp[m][m], lst[m+2], lst2[m+2];
		lst[0]=lst2[0]=0;
		lst[1]=lst2[1]=m-1;
		for(int r=m-1; r>=0; --r) {
			int akt[m+2], akt2[m+2];
			akt[0]=akt2[0]=0;
			akt[m-r+1]=akt2[m-r+1]=m-1;
			rep(p, m-r) {
				int k=p+r;
				pair<int,int>mi={INF, INF};
				for(int l=lst[p]; l<=lst[p+1]; ++l) {
					mi=min(mi, {tr[N+x][p][l]+dwa[i+1][l][k], l});
				}
				akt[p+1]=mi.nd;
				tmp[p][k]=mi.st;
				mi={INF, INF};
				for(int l=lst2[p]; l<=lst2[p+1]; ++l) {
					mi=min(mi, {tr[N+x][k][l]+dwa[i+1][l][p], l});
				}
				akt2[p+1]=mi.nd;
				tmp[k][p]=mi.st;
			}
			rep(p, m-r+2) {
				lst[p]=akt[p];
				lst2[p]=akt2[p];
			}
		}
		rep(j, m) rep(l, m) tr[N+x][j][l]=tmp[j][l];
	}
}
void liczwierzcholek(int v) {
	int lst[m+2], lst2[m+2];
	lst[0]=lst2[0]=0;
	lst[1]=lst2[1]=m-1;
	for(int r=m-1; r>=0; --r) {
		int akt[m+2], akt2[m+2];
		akt[0]=akt2[0]=0;
		akt[m-r+1]=akt2[m-r+1]=m-1;
		rep(p, m-r) {
			int k=p+r;
			pair<int,int>mi={INF, INF};
			for(int l=lst[p]; l<=lst[p+1]; ++l) {
				mi=min(mi, {tr[2*v][p][l]+tr[2*v+1][l][k], l});
			}
			akt[p+1]=mi.nd;
			tr[v][p][k]=mi.st;
			mi={INF, INF};
			for(int l=lst2[p]; l<=lst2[p+1]; ++l) {
				mi=min(mi, {tr[2*v][k][l]+tr[2*v+1][l][p], l});
			}
			akt2[p+1]=mi.nd;
			tr[v][k][p]=mi.st;
		}
		rep(p, m-r+2) {
			lst[p]=akt[p];
			lst2[p]=akt2[p];
		}
	}
}
void upd(int v) {
	liczlisc(v);
	v+=N;
	while(v>1) {
		v/=2;
		liczwierzcholek(v);
	}
}
void changeH(int a, int b, int c) {
	A[a][b]=c;
	upd(a/10);
	if(a%10==0 && a) upd(a/10-1);
}
void changeV(int a, int b, int c) {
	B[a][b]=c;
	upd(a/10);
}
int escape(int v1, int v2) {
	return tr[1][v1][v2];
}
void init(int r, int c, int H[5000][200], int V[5000][200]) {
	n=r; m=c;
	rep(i, n) rep(j, m-1) A[i][j]=H[i][j];
	rep(i, n-1) rep(j, m) B[i][j]=V[i][j];
	for(int i=n; i<=10*N; ++i) rep(j, m-1) A[i][j]=5001007;
	rep(i, N) liczlisc(i);
	for(int i=N-1; i; --i) liczwierzcholek(i);
}

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 7 ms 12620 KB Output is correct
2 Correct 8 ms 12620 KB Output is correct
3 Correct 81 ms 14136 KB Output is correct
4 Correct 8 ms 12620 KB Output is correct
5 Correct 8 ms 12620 KB Output is correct
6 Correct 3 ms 4684 KB Output is correct
7 Correct 4 ms 4684 KB Output is correct
8 Correct 4 ms 4684 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4684 KB Output is correct
2 Correct 4 ms 4684 KB Output is correct
3 Correct 3 ms 4708 KB Output is correct
4 Correct 68 ms 24184 KB Output is correct
5 Correct 71 ms 24240 KB Output is correct
6 Correct 67 ms 24256 KB Output is correct
7 Correct 70 ms 24188 KB Output is correct
8 Correct 65 ms 23236 KB Output is correct
9 Correct 70 ms 24208 KB Output is correct
10 Correct 62 ms 23148 KB Output is correct
11 Correct 150 ms 26564 KB Output is correct
12 Correct 68 ms 24264 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1728 ms 89064 KB Output is correct
2 Correct 1639 ms 88424 KB Output is correct
3 Correct 1780 ms 89036 KB Output is correct
4 Correct 1774 ms 89108 KB Output is correct
5 Correct 1808 ms 88372 KB Output is correct
6 Correct 3 ms 4684 KB Output is correct
7 Correct 4 ms 4684 KB Output is correct
8 Correct 4 ms 4684 KB Output is correct
9 Correct 3192 ms 89144 KB Output is correct
10 Correct 9 ms 11084 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21396 KB Output is correct
2 Correct 15 ms 21408 KB Output is correct
3 Correct 15 ms 21400 KB Output is correct
4 Correct 52 ms 22196 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1747 ms 88992 KB Output is correct
2 Correct 1642 ms 88348 KB Output is correct
3 Correct 1779 ms 88948 KB Output is correct
4 Correct 1785 ms 89212 KB Output is correct
5 Correct 1753 ms 88516 KB Output is correct
6 Correct 14 ms 21452 KB Output is correct
7 Correct 14 ms 21452 KB Output is correct
8 Correct 15 ms 21568 KB Output is correct
9 Correct 55 ms 22852 KB Output is correct
10 Correct 8 ms 12620 KB Output is correct
11 Correct 8 ms 12620 KB Output is correct
12 Correct 89 ms 15492 KB Output is correct
13 Correct 8 ms 12620 KB Output is correct
14 Correct 7 ms 12620 KB Output is correct
15 Correct 3 ms 4684 KB Output is correct
16 Correct 3 ms 4684 KB Output is correct
17 Correct 3 ms 4656 KB Output is correct
18 Correct 71 ms 24204 KB Output is correct
19 Correct 71 ms 24240 KB Output is correct
20 Correct 68 ms 24252 KB Output is correct
21 Correct 72 ms 24200 KB Output is correct
22 Correct 62 ms 23176 KB Output is correct
23 Correct 69 ms 24212 KB Output is correct
24 Correct 65 ms 23196 KB Output is correct
25 Correct 144 ms 26632 KB Output is correct
26 Correct 74 ms 24280 KB Output is correct
27 Correct 3213 ms 89272 KB Output is correct
28 Correct 3684 ms 104844 KB Output is correct
29 Correct 4299 ms 102596 KB Output is correct
30 Correct 4273 ms 102428 KB Output is correct
31 Correct 3633 ms 106740 KB Output is correct
32 Correct 9 ms 11084 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1785 ms 89160 KB Output is correct
2 Correct 1618 ms 88432 KB Output is correct
3 Correct 1825 ms 89152 KB Output is correct
4 Correct 1757 ms 89108 KB Output is correct
5 Correct 1715 ms 88348 KB Output is correct
6 Correct 14 ms 21452 KB Output is correct
7 Correct 14 ms 21452 KB Output is correct
8 Correct 14 ms 21504 KB Output is correct
9 Correct 51 ms 22852 KB Output is correct
10 Correct 8 ms 12604 KB Output is correct
11 Correct 8 ms 12620 KB Output is correct
12 Correct 87 ms 15500 KB Output is correct
13 Correct 9 ms 12620 KB Output is correct
14 Correct 8 ms 12620 KB Output is correct
15 Correct 5356 ms 187920 KB Output is correct
16 Correct 16106 ms 189112 KB Output is correct
17 Correct 3 ms 4684 KB Output is correct
18 Correct 4 ms 4624 KB Output is correct
19 Correct 3 ms 4684 KB Output is correct
20 Correct 71 ms 24176 KB Output is correct
21 Correct 69 ms 24208 KB Output is correct
22 Correct 72 ms 24172 KB Output is correct
23 Correct 66 ms 24260 KB Output is correct
24 Correct 67 ms 23172 KB Output is correct
25 Correct 70 ms 24256 KB Output is correct
26 Correct 61 ms 23236 KB Output is correct
27 Correct 158 ms 26524 KB Output is correct
28 Correct 68 ms 24184 KB Output is correct
29 Correct 3223 ms 89236 KB Output is correct
30 Correct 3598 ms 104860 KB Output is correct
31 Correct 13759 ms 186736 KB Output is correct
32 Correct 13683 ms 186884 KB Output is correct
33 Correct 4322 ms 102548 KB Output is correct
34 Correct 15917 ms 184060 KB Output is correct
35 Correct 4241 ms 102624 KB Output is correct
36 Correct 16196 ms 183792 KB Output is correct
37 Correct 3784 ms 106440 KB Output is correct
38 Correct 14189 ms 187088 KB Output is correct
39 Correct 10 ms 11124 KB Output is correct
40 Correct 16625 ms 183912 KB Output is correct