oj.uz

답안 #94308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94308 2019-01-17T12:52:39 Z fjzzq2002 웜뱃 (IOI13_wombats) C++14
76 / 100
 20000 ms 29772 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[73],aa;
const int B=71;
const int M=8192;
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].go=0;
	for(int t=b*B;t<=n-2&&t<(b+1)*B;++t)
		ts[b]=ts[b]*gen(t);
}
void reb()
{
	aa.go=0;
	for(int i=0;i<=(n-2)/B;++i)
		aa=aa*ts[i];
}
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);
    reb();
}
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);
	reb();
}

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

int escape(int V1, int V2) {
	return aa.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

# 결과 실행 시간 메모리 Grader output
1 Correct 1756 ms 23748 KB Output is correct
2 Correct 1798 ms 23928 KB Output is correct
3 Correct 1849 ms 25592 KB Output is correct
4 Correct 1782 ms 23788 KB Output is correct
5 Correct 1831 ms 23800 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 11 ms 8824 KB Output is correct
8 Correct 11 ms 8824 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8824 KB Output is correct
2 Correct 11 ms 8824 KB Output is correct
3 Correct 10 ms 8828 KB Output is correct
4 Correct 11 ms 8956 KB Output is correct
5 Correct 11 ms 8952 KB Output is correct
6 Correct 11 ms 8952 KB Output is correct
7 Correct 11 ms 8952 KB Output is correct
8 Correct 10 ms 8824 KB Output is correct
9 Correct 10 ms 8824 KB Output is correct
10 Correct 10 ms 8952 KB Output is correct
11 Correct 72 ms 9976 KB Output is correct
12 Correct 11 ms 8952 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 710 ms 9540 KB Output is correct
2 Correct 1078 ms 9524 KB Output is correct
3 Correct 1573 ms 9548 KB Output is correct
4 Correct 1532 ms 9540 KB Output is correct
5 Correct 1757 ms 9592 KB Output is correct
6 Correct 9 ms 8824 KB Output is correct
7 Correct 9 ms 8824 KB Output is correct
8 Correct 9 ms 8828 KB Output is correct
9 Correct 6127 ms 9564 KB Output is correct
10 Correct 11 ms 8952 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1811 ms 27724 KB Output is correct
2 Correct 1804 ms 27868 KB Output is correct
3 Correct 1820 ms 27768 KB Output is correct
4 Correct 1827 ms 28664 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 811 ms 9592 KB Output is correct
2 Correct 1061 ms 9520 KB Output is correct
3 Correct 1589 ms 9464 KB Output is correct
4 Correct 1438 ms 9464 KB Output is correct
5 Correct 1745 ms 9596 KB Output is correct
6 Correct 1875 ms 27896 KB Output is correct
7 Correct 1841 ms 27768 KB Output is correct
8 Correct 1797 ms 27640 KB Output is correct
9 Correct 1808 ms 28672 KB Output is correct
10 Correct 1814 ms 23752 KB Output is correct
11 Correct 1784 ms 23816 KB Output is correct
12 Correct 1888 ms 25436 KB Output is correct
13 Correct 1757 ms 23800 KB Output is correct
14 Correct 1785 ms 23672 KB Output is correct
15 Correct 10 ms 8824 KB Output is correct
16 Correct 10 ms 8824 KB Output is correct
17 Correct 10 ms 8824 KB Output is correct
18 Correct 11 ms 8952 KB Output is correct
19 Correct 11 ms 8952 KB Output is correct
20 Correct 11 ms 8952 KB Output is correct
21 Correct 10 ms 8828 KB Output is correct
22 Correct 11 ms 8824 KB Output is correct
23 Correct 11 ms 8952 KB Output is correct
24 Correct 11 ms 8952 KB Output is correct
25 Correct 75 ms 9972 KB Output is correct
26 Correct 11 ms 8952 KB Output is correct
27 Correct 6141 ms 9592 KB Output is correct
28 Correct 11351 ms 28724 KB Output is correct
29 Correct 14967 ms 25316 KB Output is correct
30 Correct 14785 ms 25320 KB Output is correct
31 Correct 12472 ms 29772 KB Output is correct
32 Correct 10 ms 8824 KB Output is correct

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 709 ms 9616 KB Output is correct
2 Correct 1076 ms 9520 KB Output is correct
3 Correct 1588 ms 9540 KB Output is correct
4 Correct 1443 ms 9540 KB Output is correct
5 Correct 1789 ms 9540 KB Output is correct
6 Correct 1747 ms 27680 KB Output is correct
7 Correct 1823 ms 27676 KB Output is correct
8 Correct 1828 ms 27696 KB Output is correct
9 Correct 1882 ms 29020 KB Output is correct
10 Correct 1787 ms 23728 KB Output is correct
11 Correct 1740 ms 23740 KB Output is correct
12 Correct 1862 ms 25792 KB Output is correct
13 Correct 1821 ms 23740 KB Output is correct
14 Correct 1806 ms 23744 KB Output is correct
15 Correct 3436 ms 29020 KB Output is correct
16 Execution timed out 20073 ms 29664 KB Time limit exceeded
17 Halted 0 ms 0 KB -