| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26806 |
2017-07-06T05:50:07 Z |
yutaka1999 |
Wall (CEOI14_wall) |
C++14 |
|
86 ms |
528960 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);
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
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]);
^
| # |
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 |
23 ms |
525888 KB |
Output is correct |
| 7 |
Correct |
13 ms |
524352 KB |
Output is correct |
| 8 |
Correct |
9 ms |
524352 KB |
Output is correct |
| 9 |
Correct |
9 ms |
524352 KB |
Output is correct |
| 10 |
Correct |
19 ms |
525888 KB |
Output is correct |
| 11 |
Correct |
36 ms |
525888 KB |
Output is correct |
| 12 |
Correct |
59 ms |
528960 KB |
Output is correct |
| 13 |
Correct |
46 ms |
525888 KB |
Output is correct |
| 14 |
Correct |
49 ms |
528960 KB |
Output is correct |
| 15 |
Correct |
29 ms |
528960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
528960 KB |
Output is correct |
| 2 |
Correct |
83 ms |
528960 KB |
Output is correct |
| 3 |
Correct |
39 ms |
525888 KB |
Output is correct |
| 4 |
Correct |
46 ms |
528960 KB |
Output is correct |
| 5 |
Correct |
69 ms |
528960 KB |
Output is correct |
| 6 |
Correct |
66 ms |
528960 KB |
Output is correct |
| 7 |
Correct |
86 ms |
528960 KB |
Output is correct |
| 8 |
Correct |
76 ms |
528960 KB |
Output is correct |
| 9 |
Correct |
46 ms |
525888 KB |
Output is correct |
| 10 |
Correct |
46 ms |
528960 KB |
Output is correct |
| 11 |
Correct |
56 ms |
528960 KB |
Output is correct |
| 12 |
Correct |
76 ms |
528960 KB |
Output is correct |
| 13 |
Correct |
59 ms |
528960 KB |
Output is correct |
| 14 |
Correct |
86 ms |
528960 KB |
Output is correct |
| 15 |
Correct |
39 ms |
525888 KB |
Output is correct |
| 16 |
Correct |
43 ms |
525888 KB |
Output is correct |
| 17 |
Correct |
53 ms |
528960 KB |
Output is correct |
| 18 |
Correct |
63 ms |
528960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 9 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 10 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 11 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 12 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 13 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 14 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 15 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 16 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 17 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 18 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 19 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
| 20 |
Incorrect |
0 ms |
522732 KB |
Output isn't correct |
