Submission #26804

#TimeUsernameProblemLanguageResultExecution timeMemory
26804yutaka1999Wall (CEOI14_wall)C++14
10 / 100
2000 ms1048576 KiB
#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 (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: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]);
                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...