oj.uz

Submission #26804

# Submission time Handle Problem Language Result Execution time Memory
26804 2017-07-06T05:36:45 Z yutaka1999 Wall (CEOI14_wall) C++14
10 / 100
 2000 ms 1048576 KB 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define SIZE 405
#define INF 100000000000000000LL

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;
typedef pair <P,P> PP;

int A[SIZE][SIZE];
int rt[SIZE][SIZE];
int down[SIZE][SIZE];
int right[SIZE][SIZE];
int tp[SIZE],bt[SIZE];
ll dist[SIZE][SIZE][SIZE];
ll dp[2][SIZE];

int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			scanf("%d",&A[i][j]);
		}
	}
	for(int i=0;i<m;i++)
	{
		rt[0][i]=0;
		for(int j=0;j<n;j++)
		{
			rt[j+1][i]=rt[j][i]+A[j][i];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			scanf("%d",&down[i][j]);
		}
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<m;j++)
		{
			scanf("%d",&right[i][j]);
		}
	}
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			ll sum=0;
			for(int k=j;k<=n;k++)
			{
				dist[i][j][k]=sum;
				if(k<n) sum+=down[k][i];
			}
		}
	}
	priority_queue <PP,vector <PP>,greater <PP> > que;
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			for(int k=j;k<=n;k++) que.push(PP(P(dist[i][j][k],i),P(j,k)));
		}
	}
	while(!que.empty())
	{
		PP p=que.top();que.pop();
		int x=p.first.second,s=p.second.first,t=p.second.second;
		if(dist[x][s][t]<p.first.first) continue;
		if(s>0&&dist[x][s-1][t]>dist[x][s][t]+down[s-1][x])
		{
			dist[x][s-1][t]=dist[x][s][t]+down[s-1][x];
			que.push(PP(P(dist[x][s-1][t],x),P(s-1,t)));
		}
		if(s+1<=t&&dist[x][s+1][t]>dist[x][s][t]+down[s][x])
		{
			dist[x][s+1][t]=dist[x][s][t]+down[s][x];
			que.push(PP(P(dist[x][s+1][t],x),P(s+1,t)));
		}
		if(s<=t-1&&dist[x][s][t-1]>dist[x][s][t]+down[t-1][x])
		{
			dist[x][s][t-1]=dist[x][s][t]+down[t-1][x];
			que.push(PP(P(dist[x][s][t-1],x),P(s,t-1)));
		}
		if(t+1<=n&&dist[x][s][t+1]>dist[x][s][t]+down[t][x])
		{
			dist[x][s][t+1]=dist[x][s][t]+down[t][x];
			que.push(PP(P(dist[x][s][t+1],x),P(s,t+1)));
		}
		if(x>0&&rt[s][x-1]==rt[t][x-1]&&dist[x-1][s][t]>dist[x][s][t]+right[s][x-1]+right[t][x-1])
		{
			dist[x-1][s][t]=dist[x][s][t]+right[s][x-1]+right[t][x-1];
			que.push(PP(P(dist[x-1][s][t],x-1),P(s,t)));
		}
		if(x+1<=m&&rt[s][x]==rt[t][x]&&dist[x+1][s][t]>dist[x][s][t]+right[s][x]+right[t][x])
		{
			dist[x+1][s][t]=dist[x][s][t]+right[s][x]+right[t][x];
			que.push(PP(P(dist[x+1][s][t],x+1),P(s,t)));
		}
	}/*
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			for(int k=j+1;k<=n;k++)
			{
				if(i==3) printf("[%d %d %d] %lld\n",i,j,k,dist[i][j][k]);
			}
		}
	}*/
	int mx=0;
	for(int i=0;i<m;i++)
	{
		tp[i]=n,bt[i]=0;
		for(int j=0;j<n;j++)
		{
			if(A[j][i]==1)
			{
				tp[i]=min(tp[i],j);
				bt[i]=max(bt[i],j);
				mx=max(mx,i+1);
			}
		}
	}
	int pos=0;
	for(int i=0;i<=n;i++)
	{
		dp[pos][i]=dist[0][0][i];
	}
	for(int i=1;i<=mx;i++)
	{
		pos^=1;
		for(int j=0;j<=bt[i-1];j++) dp[pos][j]=INF;
		for(int j=bt[i-1]+1;j<=n;j++) dp[pos][j]=dp[pos^1][j]+right[j][i-1];
		//for(int j=0;j<=n;j++) printf("%lld ",dp[pos][j]>=INF?-1:dp[pos][j]);puts("");
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=n;k++)
			{
				ll d=dist[i][min(j,k)][max(j,k)];
				dp[pos][k]=min(dp[pos][k],dp[pos][j]+d);
			}
		}
	}
	for(int i=mx-1;i>=0;i--)
	{
		pos^=1;
		for(int j=0;j<=tp[i];j++) dp[pos][j]=dp[pos^1][j]+right[j][i];
		for(int j=tp[i]+1;j<=n;j++) dp[pos][j]=INF;
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=n;k++)
			{
				ll d=dist[i][min(j,k)][max(j,k)];
				dp[pos][k]=min(dp[pos][k],dp[pos][j]+d);
			}
		}
	}
	printf("%lld\n",dp[pos][0]);
	return 0;
}

Compilation message

wall.cpp: In function 'int main()':
wall.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
wall.cpp:31:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&A[i][j]);
                        ^
wall.cpp:46:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&down[i][j]);
                           ^
wall.cpp:53:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&right[i][j]);
                            ^

Subtask #1
10.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 522872 KB Output is correct
2 Correct 0 ms 522872 KB Output is correct
3 Correct 0 ms 522872 KB Output is correct
4 Correct 0 ms 522872 KB Output is correct
5 Correct 0 ms 522872 KB Output is correct
6 Correct 6 ms 523584 KB Output is correct
7 Incorrect 3 ms 523584 KB Output isn't correct
8 Incorrect 3 ms 523584 KB Output isn't correct
9 Correct 3 ms 523584 KB Output is correct
10 Correct 6 ms 524352 KB Output is correct
11 Incorrect 9 ms 524352 KB Output isn't correct
12 Correct 16 ms 524352 KB Output is correct
13 Correct 16 ms 525888 KB Output is correct
14 Incorrect 23 ms 524352 KB Output isn't correct
15 Incorrect 13 ms 524352 KB Output isn't correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 524352 KB Output isn't correct
2 Correct 26 ms 525888 KB Output is correct
3 Incorrect 16 ms 525888 KB Output isn't correct
4 Correct 16 ms 525888 KB Output is correct
5 Correct 19 ms 525888 KB Output is correct
6 Incorrect 19 ms 525888 KB Output isn't correct
7 Incorrect 19 ms 525888 KB Output isn't correct
8 Correct 19 ms 524352 KB Output is correct
9 Correct 16 ms 524352 KB Output is correct
10 Correct 19 ms 525888 KB Output is correct
11 Correct 19 ms 525888 KB Output is correct
12 Correct 19 ms 525888 KB Output is correct
13 Incorrect 19 ms 525888 KB Output isn't correct
14 Correct 16 ms 525888 KB Output is correct
15 Incorrect 13 ms 525888 KB Output isn't correct
16 Incorrect 16 ms 525888 KB Output isn't correct
17 Incorrect 16 ms 525888 KB Output isn't correct
18 Incorrect 16 ms 525888 KB Output isn't correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 719424 KB Execution timed out
2 Execution timed out 2000 ms 719424 KB Execution timed out
3 Execution timed out 2000 ms 719424 KB Execution timed out
4 Execution timed out 2000 ms 719424 KB Execution timed out
5 Memory limit exceeded 333 ms 1048576 KB Memory limit exceeded
6 Execution timed out 2000 ms 719424 KB Execution timed out
7 Memory limit exceeded 299 ms 1048576 KB Memory limit exceeded
8 Memory limit exceeded 276 ms 1048576 KB Memory limit exceeded
9 Memory limit exceeded 386 ms 1048576 KB Memory limit exceeded
10 Memory limit exceeded 293 ms 1048576 KB Memory limit exceeded
11 Memory limit exceeded 276 ms 1048576 KB Memory limit exceeded
12 Execution timed out 2000 ms 719424 KB Execution timed out
13 Memory limit exceeded 286 ms 1048576 KB Memory limit exceeded
14 Memory limit exceeded 356 ms 1048576 KB Memory limit exceeded
15 Memory limit exceeded 379 ms 1048576 KB Memory limit exceeded
16 Memory limit exceeded 396 ms 1048576 KB Memory limit exceeded
17 Memory limit exceeded 363 ms 1048576 KB Memory limit exceeded
18 Memory limit exceeded 386 ms 1048576 KB Memory limit exceeded
19 Memory limit exceeded 393 ms 1048576 KB Memory limit exceeded
20 Memory limit exceeded 373 ms 1048576 KB Memory limit exceeded