oj.uz

Submission #94310

# Submission time Handle Problem Language Result Execution time Memory
94310 2019-01-17T12:55:29 Z fjzzq2002 Wombats (IOI13_wombats) C++14
100 / 100
 12627 ms 182724 KB 
#pragma GCC optimize("-Ofast","-funroll-all-loops","-fno-stack-protector")
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,r[5000][200],d[5000][200];
void cmin(int&a,int b) {if(a>b)a=b;}
struct ini
{
int s[200][200];
bool go;
}ts[1028],aa;
const int M=512;
const int B=10;
inline ini gen(int t)
{
	//r[t],r[t+1],d[t]
	ini u; u.go=1;
	for(int i=0;i<m;++i)
	{
		u.s[i][i]=d[t][i];
		for(int j=i;j+1<m;++j)
			u.s[i][j+1]=u.s[i][j]+r[t+1][j];
		for(int j=i-1;j>=0;--j)
			u.s[i][j]=u.s[i][j+1]+r[t+1][j];
	}
	for(int i=0;i<m;++i)
	{
		for(int j=0;j+1<m;++j)
			cmin(u.s[j+1][i],u.s[j][i]+r[t][j]);
		for(int j=m-2;j>=0;--j)
			cmin(u.s[j][i],u.s[j+1][i]+r[t][j]);
	}
	return u;
}
typedef pair<int,int> pii;
void cmin(pii&a,pii b) {if(a>b)a=b;}
#define fi first
#define se second
inline ini operator * (const ini&a,const ini&b)
{
	static pii ts[200][200];
	if(!a.go) return b;
	if(!b.go) return a;
	//(a-1,b) (a,b) (a,b+1)
	for(int i=0;i<m;++i) //(0,i)
	{
		int x=0,y=i; pii&u=ts[x][y]; u=pii(2.1e9,0);
		for(int k=0;k<m;++k)
			cmin(u,pii(a.s[x][k]+b.s[k][y],k));
	}
	for(int i=0;i<m;++i) //(i,m-1)
	{
		int x=i,y=m-1; pii&u=ts[x][y]; u=pii(2.1e9,0);
		for(int k=0;k<m;++k)
			cmin(u,pii(a.s[x][k]+b.s[k][y],k));
	}
	for(int s=m;s>=-m;--s)
	{
		for(int i=1;i<m;++i)
		{
			int j=i+s;
			if(j>=m-1||j<0) continue;
			pii&u=ts[i][j]; u=pii(2.1e9,0);
			for(int k=min(ts[i-1][j].se,ts[i][j+1].se);
			k<=ts[i][j+1].se;++k)
				cmin(u,pii(a.s[i][k]+b.s[k][j],k));
		}
	}
	ini u; u.go=1;
	for(int i=0;i<m;++i)
		for(int j=0;j<m;++j)
			u.s[i][j]=ts[i][j].fi;
	return u;
}
void reb(int b)
{
	ts[b+M].go=0;
	for(int t=b*B;t<=n-2&&t<(b+1)*B;++t)
		ts[b+M]=ts[b+M]*gen(t);
	for(int j=(b+M)>>1;j;j>>=1)
		ts[j]=ts[j+j]*ts[j+j+1];
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n=R; m=C;
    memcpy(r,H,sizeof r);
    memcpy(d,V,sizeof d);
    for(int i=0;i<=(n-2)/B;++i) reb(i);
}
void changeH(int P, int Q, int W) {
	r[P][Q]=W;
	reb(P/B);
	if(P-1>=0&&P/B!=(P-1)/B)
		reb((P-1)/B);
}

void changeV(int P, int Q, int W) {
	d[P][Q]=W; reb(P/B);
}

int escape(int V1, int V2) {
	return ts[1].s[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]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 169208 KB Output is correct
2 Correct 619 ms 169268 KB Output is correct
3 Correct 692 ms 171324 KB Output is correct
4 Correct 650 ms 169084 KB Output is correct
5 Correct 632 ms 169208 KB Output is correct
6 Correct 12 ms 10148 KB Output is correct
7 Correct 11 ms 10104 KB Output is correct
8 Correct 11 ms 10104 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10076 KB Output is correct
2 Correct 11 ms 10104 KB Output is correct
3 Correct 11 ms 10232 KB Output is correct
4 Correct 12 ms 10360 KB Output is correct
5 Correct 13 ms 10332 KB Output is correct
6 Correct 12 ms 10360 KB Output is correct
7 Correct 12 ms 10360 KB Output is correct
8 Correct 13 ms 10320 KB Output is correct
9 Correct 12 ms 10364 KB Output is correct
10 Correct 12 ms 10268 KB Output is correct
11 Correct 77 ms 12024 KB Output is correct
12 Correct 13 ms 10388 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 13100 KB Output is correct
2 Correct 253 ms 13048 KB Output is correct
3 Correct 380 ms 13176 KB Output is correct
4 Correct 349 ms 13048 KB Output is correct
5 Correct 362 ms 13092 KB Output is correct
6 Correct 11 ms 10104 KB Output is correct
7 Correct 11 ms 10104 KB Output is correct
8 Correct 11 ms 10104 KB Output is correct
9 Correct 1259 ms 13176 KB Output is correct
10 Correct 12 ms 10104 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 173148 KB Output is correct
2 Correct 640 ms 173176 KB Output is correct
3 Correct 610 ms 173304 KB Output is correct
4 Correct 620 ms 174456 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 13176 KB Output is correct
2 Correct 246 ms 13020 KB Output is correct
3 Correct 371 ms 13120 KB Output is correct
4 Correct 355 ms 13180 KB Output is correct
5 Correct 356 ms 13048 KB Output is correct
6 Correct 661 ms 173164 KB Output is correct
7 Correct 619 ms 173084 KB Output is correct
8 Correct 676 ms 173176 KB Output is correct
9 Correct 662 ms 174712 KB Output is correct
10 Correct 626 ms 169208 KB Output is correct
11 Correct 615 ms 169248 KB Output is correct
12 Correct 677 ms 171528 KB Output is correct
13 Correct 645 ms 169208 KB Output is correct
14 Correct 627 ms 169208 KB Output is correct
15 Correct 11 ms 10104 KB Output is correct
16 Correct 12 ms 10104 KB Output is correct
17 Correct 12 ms 10148 KB Output is correct
18 Correct 13 ms 10360 KB Output is correct
19 Correct 13 ms 10360 KB Output is correct
20 Correct 13 ms 10360 KB Output is correct
21 Correct 11 ms 10276 KB Output is correct
22 Correct 11 ms 10360 KB Output is correct
23 Correct 13 ms 10360 KB Output is correct
24 Correct 13 ms 10360 KB Output is correct
25 Correct 77 ms 12024 KB Output is correct
26 Correct 12 ms 10332 KB Output is correct
27 Correct 1263 ms 13148 KB Output is correct
28 Correct 2872 ms 174568 KB Output is correct
29 Correct 3443 ms 145176 KB Output is correct
30 Correct 3404 ms 145244 KB Output is correct
31 Correct 3097 ms 176056 KB Output is correct
32 Correct 12 ms 10104 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 13180 KB Output is correct
2 Correct 253 ms 13176 KB Output is correct
3 Correct 376 ms 13048 KB Output is correct
4 Correct 339 ms 13048 KB Output is correct
5 Correct 369 ms 13180 KB Output is correct
6 Correct 642 ms 173324 KB Output is correct
7 Correct 612 ms 173048 KB Output is correct
8 Correct 670 ms 173068 KB Output is correct
9 Correct 670 ms 174456 KB Output is correct
10 Correct 621 ms 169208 KB Output is correct
11 Correct 620 ms 169208 KB Output is correct
12 Correct 674 ms 171404 KB Output is correct
13 Correct 651 ms 169120 KB Output is correct
14 Correct 629 ms 169376 KB Output is correct
15 Correct 4241 ms 174552 KB Output is correct
16 Correct 12627 ms 176824 KB Output is correct
17 Correct 12 ms 10104 KB Output is correct
18 Correct 10 ms 10104 KB Output is correct
19 Correct 10 ms 10104 KB Output is correct
20 Correct 12 ms 10360 KB Output is correct
21 Correct 11 ms 10360 KB Output is correct
22 Correct 11 ms 10360 KB Output is correct
23 Correct 11 ms 10360 KB Output is correct
24 Correct 13 ms 10360 KB Output is correct
25 Correct 13 ms 10360 KB Output is correct
26 Correct 13 ms 10360 KB Output is correct
27 Correct 77 ms 12664 KB Output is correct
28 Correct 13 ms 10332 KB Output is correct
29 Correct 1253 ms 13248 KB Output is correct
30 Correct 2950 ms 177612 KB Output is correct
31 Correct 9071 ms 182132 KB Output is correct
32 Correct 9181 ms 181992 KB Output is correct
33 Correct 3413 ms 148112 KB Output is correct
34 Correct 11783 ms 152164 KB Output is correct
35 Correct 3387 ms 148012 KB Output is correct
36 Correct 11526 ms 152140 KB Output is correct
37 Correct 3196 ms 179200 KB Output is correct
38 Correct 10680 ms 182724 KB Output is correct
39 Correct 12 ms 10104 KB Output is correct
40 Correct 11983 ms 152416 KB Output is correct