oj.uz

Submission #94307

# Submission time Handle Problem Language Result Execution time Memory
94307 2019-01-17T12:45:36 Z fjzzq2002 Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 33088 KB 
#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;
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
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

# Verdict Execution time Memory Grader output
1 Correct 1808 ms 23772 KB Output is correct
2 Correct 1764 ms 23752 KB Output is correct
3 Correct 1857 ms 26488 KB Output is correct
4 Correct 1826 ms 23844 KB Output is correct
5 Correct 1795 ms 23800 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 10 ms 8824 KB Output is correct
8 Correct 10 ms 8824 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8824 KB Output is correct
2 Correct 10 ms 8824 KB Output is correct
3 Correct 9 ms 8740 KB Output is correct
4 Correct 11 ms 8952 KB Output is correct
5 Correct 11 ms 8952 KB Output is correct
6 Correct 12 ms 8952 KB Output is correct
7 Correct 11 ms 8952 KB Output is correct
8 Correct 11 ms 8824 KB Output is correct
9 Correct 11 ms 8952 KB Output is correct
10 Correct 11 ms 8952 KB Output is correct
11 Correct 75 ms 11248 KB Output is correct
12 Correct 11 ms 8952 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 9720 KB Output is correct
2 Correct 1120 ms 9460 KB Output is correct
3 Correct 1618 ms 9572 KB Output is correct
4 Correct 1453 ms 9480 KB Output is correct
5 Correct 1812 ms 9472 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 10 ms 8824 KB Output is correct
8 Correct 10 ms 8824 KB Output is correct
9 Correct 6328 ms 9468 KB Output is correct
10 Correct 11 ms 8824 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1814 ms 27812 KB Output is correct
2 Correct 1754 ms 27900 KB Output is correct
3 Correct 1851 ms 27768 KB Output is correct
4 Correct 1844 ms 29048 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 9584 KB Output is correct
2 Correct 1137 ms 9336 KB Output is correct
3 Correct 1592 ms 9464 KB Output is correct
4 Correct 1488 ms 9464 KB Output is correct
5 Correct 1793 ms 9468 KB Output is correct
6 Correct 1850 ms 27868 KB Output is correct
7 Correct 1725 ms 27640 KB Output is correct
8 Correct 1830 ms 27856 KB Output is correct
9 Correct 1831 ms 29200 KB Output is correct
10 Correct 1758 ms 23800 KB Output is correct
11 Correct 1830 ms 23672 KB Output is correct
12 Correct 1837 ms 26488 KB Output is correct
13 Correct 1788 ms 23804 KB Output is correct
14 Correct 1791 ms 23800 KB Output is correct
15 Correct 10 ms 8824 KB Output is correct
16 Correct 10 ms 8824 KB Output is correct
17 Correct 9 ms 8824 KB Output is correct
18 Correct 10 ms 8824 KB Output is correct
19 Correct 10 ms 8824 KB Output is correct
20 Correct 10 ms 8824 KB Output is correct
21 Correct 10 ms 8824 KB Output is correct
22 Correct 10 ms 8952 KB Output is correct
23 Correct 10 ms 8824 KB Output is correct
24 Correct 10 ms 8860 KB Output is correct
25 Correct 72 ms 11256 KB Output is correct
26 Correct 10 ms 8824 KB Output is correct
27 Correct 6346 ms 9464 KB Output is correct
28 Correct 11739 ms 32116 KB Output is correct
29 Correct 14686 ms 28520 KB Output is correct
30 Correct 14689 ms 28420 KB Output is correct
31 Correct 12546 ms 33088 KB Output is correct
32 Correct 11 ms 8824 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 9464 KB Output is correct
2 Correct 1111 ms 9592 KB Output is correct
3 Correct 1615 ms 9464 KB Output is correct
4 Correct 1449 ms 9564 KB Output is correct
5 Correct 1808 ms 9592 KB Output is correct
6 Correct 1846 ms 27896 KB Output is correct
7 Correct 1812 ms 27768 KB Output is correct
8 Correct 1856 ms 27768 KB Output is correct
9 Correct 1867 ms 29352 KB Output is correct
10 Correct 1775 ms 23800 KB Output is correct
11 Correct 1769 ms 23800 KB Output is correct
12 Correct 1785 ms 26520 KB Output is correct
13 Correct 1843 ms 23796 KB Output is correct
14 Correct 2017 ms 23828 KB Output is correct
15 Correct 3648 ms 31856 KB Output is correct
16 Execution timed out 20010 ms 32448 KB Time limit exceeded
17 Halted 0 ms 0 KB -