oj.uz

답안 #26802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26802 2017-07-06T05:30:20 Z yutaka1999 Wall (CEOI14_wall) C++14
0 / 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++)
	{
		rt[i][0]=0;
		for(int j=0;j<m;j++)
		{
			scanf("%d",&A[i][j]);
			rt[i][j+1]=rt[i][j]+A[i][j];
		}
	}
	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<=m&&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[x-1][s]==rt[x-1][t]&&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[x][s]==rt[x][t]&&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: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:40: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:47: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
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 522872 KB Output is correct
2 Incorrect 0 ms 522872 KB Output isn't 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 Incorrect 9 ms 523584 KB Output isn't correct
7 Incorrect 3 ms 523584 KB Output isn't correct
8 Incorrect 3 ms 523584 KB Output isn't correct
9 Incorrect 3 ms 523584 KB Output isn't correct
10 Incorrect 6 ms 524352 KB Output isn't correct
11 Incorrect 13 ms 524352 KB Output isn't correct
12 Incorrect 16 ms 524352 KB Output isn't correct
13 Correct 13 ms 525888 KB Output is correct
14 Incorrect 23 ms 525888 KB Output isn't correct
15 Incorrect 16 ms 524352 KB Output isn't correct

Subtask #2
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 524352 KB Output isn't correct
2 Incorrect 23 ms 525888 KB Output isn't correct
3 Incorrect 16 ms 525888 KB Output isn't correct
4 Incorrect 13 ms 525888 KB Output isn't correct
5 Correct 23 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 Incorrect 19 ms 524352 KB Output isn't correct
9 Incorrect 13 ms 524352 KB Output isn't correct
10 Correct 16 ms 525888 KB Output is correct
11 Incorrect 19 ms 525888 KB Output isn't correct
12 Incorrect 19 ms 525888 KB Output isn't correct
13 Incorrect 19 ms 525888 KB Output isn't correct
14 Incorrect 19 ms 525888 KB Output isn't correct
15 Incorrect 16 ms 525888 KB Output isn't correct
16 Incorrect 23 ms 525888 KB Output isn't correct
17 Incorrect 26 ms 525888 KB Output isn't correct
18 Incorrect 13 ms 525888 KB Output isn't correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 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 1096 ms 1048576 KB Memory limit exceeded
6 Execution timed out 2000 ms 719424 KB Execution timed out
7 Memory limit exceeded 289 ms 1048576 KB Memory limit exceeded
8 Memory limit exceeded 303 ms 1048576 KB Memory limit exceeded
9 Memory limit exceeded 283 ms 1048576 KB Memory limit exceeded
10 Memory limit exceeded 273 ms 1048576 KB Memory limit exceeded
11 Memory limit exceeded 263 ms 1048576 KB Memory limit exceeded
12 Execution timed out 2000 ms 719424 KB Execution timed out
13 Memory limit exceeded 316 ms 1048576 KB Memory limit exceeded
14 Memory limit exceeded 606 ms 1048576 KB Memory limit exceeded
15 Memory limit exceeded 316 ms 1048576 KB Memory limit exceeded
16 Memory limit exceeded 343 ms 1048576 KB Memory limit exceeded
17 Memory limit exceeded 396 ms 1048576 KB Memory limit exceeded
18 Memory limit exceeded 333 ms 1048576 KB Memory limit exceeded
19 Memory limit exceeded 383 ms 1048576 KB Memory limit exceeded
20 Memory limit exceeded 359 ms 1048576 KB Memory limit exceeded