| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26802 |
2017-07-06T05:30:20 Z |
yutaka1999 |
Wall (CEOI14_wall) |
C++14 |
|
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]);
^
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
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 |
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 |
