Submission #26806

#	Time	Username	Problem	Language	Result	Execution time	Memory
26806		yutaka1999	Wall (CEOI14_wall)	C++14	60 / 100	86 ms	528960 KiB

wall

#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);
	if(n>40||m>40) return 0;
	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;
		for(int i=0;i<=n;i++)
		{
			ll vl=dist[x][s][t]+dist[x][min(s,i)][max(s,i)];
			int a=min(i,t),b=max(i,t);
			if(vl<dist[x][a][b])
			{
				dist[x][a][b]=vl;
				que.push(PP(P(vl,x),P(a,b)));
			}
		}
		for(int i=0;i<=n;i++)
		{
			ll vl=dist[x][s][t]+dist[x][min(t,i)][max(t,i)];
			int a=min(i,s),b=max(i,s);
			if(vl<dist[x][a][b])
			{
				dist[x][a][b]=vl;
				que.push(PP(P(vl,x),P(a,b)));
			}
		}
		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 (stderr)

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:32: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:47: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:54: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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40