oj.uz

Submission #437439

# Submission time Handle Problem Language Result Execution time Memory
437439 2021-06-26T10:17:50 Z RainAir Wombats (IOI13_wombats) C++11
100 / 100
 7053 ms 236872 KB 
#include "wombats.h"
#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000 + 5;
const int MAXM = 200 + 5;
const int B = 16;
#define lc ((x)<<1)
#define rc ((x)<<1|1)

int n,m;

struct Matrix{
	int a[MAXM][MAXM];// i列走到j列
	Matrix(){CLR(a,0);}

	Matrix operator * (const Matrix &t) const {
		Matrix res;// res.a[i][j]=  min(a[i][k]+t.a[k][j])
		static int ps[MAXM][MAXM];FOR(i,0,m+1) FOR(j,0,m+1) ps[i][j] = -1;
		FOR(l,1,m){
			ROF(r,m,1){
				// ps[l-1][r] <= ps[l][r] <= ps[l][r+1]
				int ll = 1,rr = m;
				if(ps[l-1][r] != -1) ll = ps[l-1][r];
				if(ps[l][r+1] != -1) rr = ps[l][r+1];
				res.a[l][r] = 1e9;
				FOR(k,ll,rr){
					if(res.a[l][r] > a[l][k]+t.a[k][r]){
						res.a[l][r] = a[l][k]+t.a[k][r];
						ps[l][r] = k;
					}
				}
			}
		}
		return res;
	}
}sm[1252];

int H[MAXN][MAXM],C[MAXN][MAXM];

inline Matrix gen(int i){
	// 第 i 行
	Matrix res;
	FOR(l,1,m){
		int sm = 0;
		FOR(r,l,m){
			res.a[l][r] = sm;
			sm += H[i][r];
		}
		sm = 0;
		ROF(r,l-1,1){
			sm += H[i][r];
			res.a[l][r] = sm;
		}
	}
	FOR(l,1,m) FOR(r,1,m) res.a[l][r] += C[i][r];
	return res;
}

inline Matrix rebuild(int x){
	Matrix res=gen((x-1)*B+1);
	FOR(i,(x-1)*B+2,std::min(n,x*B)) res = res*gen(i);
	return res;
}

inline void build(int x,int l,int r){
	if(l == r) return (void)(sm[x] = rebuild(l));
	int mid = (l + r) >> 1;
	build(lc,l,mid);build(rc,mid+1,r);
	sm[x] = sm[lc]*sm[rc];
}

inline void update(int x,int l,int r,int p){
	if(l == r) return (void)(sm[x] = rebuild(l));
	int mid = (l + r) >> 1;
	if(p <= mid) update(lc,l,mid,p);
	else update(rc,mid+1,r,p);
	sm[x] = sm[lc]*sm[rc];
}

int bel[MAXN];

void init(int RR,int CC,int h[5000][200],int c[5000][200]){
	n = RR;m = CC;
	FOR(i,1,n) FOR(j,1,m-1) H[i][j] = h[i-1][j-1];
	FOR(i,1,n-1) FOR(j,1,m) C[i][j] = c[i-1][j-1];
	FOR(i,1,n) bel[i] = (i-1)/B+1;
	build(1,1,bel[n]);
}

void changeH(int p,int q,int w){
	++p;++q;H[p][q] = w;
	update(1,1,bel[n],bel[p]);
}

void changeV(int p,int q,int w){
	++p;++q;C[p][q] = w;
	update(1,1,bel[n],bel[p]);
}

int escape(int p,int q){
	++p;++q;
	return sm[1].a[p][q];
}

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 490 ms 217796 KB Output is correct
2 Correct 488 ms 217816 KB Output is correct
3 Correct 555 ms 220592 KB Output is correct
4 Correct 493 ms 217896 KB Output is correct
5 Correct 480 ms 217872 KB Output is correct
6 Correct 104 ms 206808 KB Output is correct
7 Correct 101 ms 206824 KB Output is correct
8 Correct 105 ms 206832 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 206800 KB Output is correct
2 Correct 110 ms 206832 KB Output is correct
3 Correct 106 ms 206788 KB Output is correct
4 Correct 110 ms 207300 KB Output is correct
5 Correct 118 ms 207300 KB Output is correct
6 Correct 106 ms 207208 KB Output is correct
7 Correct 109 ms 207216 KB Output is correct
8 Correct 108 ms 207276 KB Output is correct
9 Correct 107 ms 207248 KB Output is correct
10 Correct 123 ms 207196 KB Output is correct
11 Correct 186 ms 209584 KB Output is correct
12 Correct 101 ms 207200 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 208372 KB Output is correct
2 Correct 287 ms 208324 KB Output is correct
3 Correct 389 ms 208280 KB Output is correct
4 Correct 358 ms 208364 KB Output is correct
5 Correct 340 ms 208356 KB Output is correct
6 Correct 106 ms 206788 KB Output is correct
7 Correct 108 ms 206800 KB Output is correct
8 Correct 102 ms 206888 KB Output is correct
9 Correct 970 ms 208360 KB Output is correct
10 Correct 104 ms 206872 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 225776 KB Output is correct
2 Correct 512 ms 225764 KB Output is correct
3 Correct 530 ms 225788 KB Output is correct
4 Correct 523 ms 227132 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 208364 KB Output is correct
2 Correct 275 ms 208324 KB Output is correct
3 Correct 327 ms 208304 KB Output is correct
4 Correct 323 ms 208364 KB Output is correct
5 Correct 332 ms 208360 KB Output is correct
6 Correct 501 ms 225860 KB Output is correct
7 Correct 472 ms 225672 KB Output is correct
8 Correct 507 ms 225784 KB Output is correct
9 Correct 526 ms 227192 KB Output is correct
10 Correct 478 ms 217808 KB Output is correct
11 Correct 466 ms 217832 KB Output is correct
12 Correct 561 ms 220596 KB Output is correct
13 Correct 496 ms 217820 KB Output is correct
14 Correct 477 ms 217820 KB Output is correct
15 Correct 106 ms 206856 KB Output is correct
16 Correct 106 ms 206880 KB Output is correct
17 Correct 114 ms 206924 KB Output is correct
18 Correct 102 ms 207228 KB Output is correct
19 Correct 106 ms 207196 KB Output is correct
20 Correct 107 ms 207228 KB Output is correct
21 Correct 108 ms 207192 KB Output is correct
22 Correct 107 ms 207260 KB Output is correct
23 Correct 118 ms 207220 KB Output is correct
24 Correct 107 ms 207300 KB Output is correct
25 Correct 195 ms 209644 KB Output is correct
26 Correct 102 ms 207300 KB Output is correct
27 Correct 955 ms 208396 KB Output is correct
28 Correct 1894 ms 230032 KB Output is correct
29 Correct 2064 ms 226492 KB Output is correct
30 Correct 2129 ms 226848 KB Output is correct
31 Correct 1970 ms 231652 KB Output is correct
32 Correct 104 ms 206836 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 208360 KB Output is correct
2 Correct 291 ms 208348 KB Output is correct
3 Correct 334 ms 208248 KB Output is correct
4 Correct 332 ms 208364 KB Output is correct
5 Correct 318 ms 208464 KB Output is correct
6 Correct 493 ms 225880 KB Output is correct
7 Correct 492 ms 225876 KB Output is correct
8 Correct 484 ms 225804 KB Output is correct
9 Correct 505 ms 227128 KB Output is correct
10 Correct 501 ms 217816 KB Output is correct
11 Correct 475 ms 217812 KB Output is correct
12 Correct 585 ms 220532 KB Output is correct
13 Correct 485 ms 217876 KB Output is correct
14 Correct 465 ms 217812 KB Output is correct
15 Correct 2047 ms 235760 KB Output is correct
16 Correct 7053 ms 236872 KB Output is correct
17 Correct 109 ms 206788 KB Output is correct
18 Correct 104 ms 206860 KB Output is correct
19 Correct 102 ms 206880 KB Output is correct
20 Correct 108 ms 207216 KB Output is correct
21 Correct 105 ms 207356 KB Output is correct
22 Correct 109 ms 207300 KB Output is correct
23 Correct 114 ms 207292 KB Output is correct
24 Correct 100 ms 207204 KB Output is correct
25 Correct 104 ms 207304 KB Output is correct
26 Correct 103 ms 207428 KB Output is correct
27 Correct 190 ms 209648 KB Output is correct
28 Correct 102 ms 207288 KB Output is correct
29 Correct 993 ms 208356 KB Output is correct
30 Correct 1847 ms 230024 KB Output is correct
31 Correct 5698 ms 234236 KB Output is correct
32 Correct 5691 ms 234264 KB Output is correct
33 Correct 2053 ms 226428 KB Output is correct
34 Correct 6248 ms 230568 KB Output is correct
35 Correct 2176 ms 226760 KB Output is correct
36 Correct 6400 ms 230820 KB Output is correct
37 Correct 2050 ms 231796 KB Output is correct
38 Correct 5713 ms 234928 KB Output is correct
39 Correct 109 ms 206916 KB Output is correct
40 Correct 6838 ms 230724 KB Output is correct