/ tabris /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Accepted 7ms 324.0 KiB
#2 Wrong Answer 7ms 308.0 KiB
#3 Wrong Answer 285ms 38.41 MiB
#4 Wrong Answer 322ms 25.316 MiB
#5 Wrong Answer 335ms 34.453 MiB

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxN=1e6+5;
int N,M;
LL a[maxN],dp1[maxN],dp2[maxN],dp3[maxN],dp4[maxN];
int getid(int i,int j)
{
    return (i-1)*M+j;
}

int main()
{
    int cas=1;
    while(~scanf("%d%d",&N,&M))
    {
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++)scanf("%lld",&a[getid(i,j)]);

        for(int j=2;j<=M-1;j++)dp1[getid(2,j)]=a[getid(2,j)]+a[getid(1,j+1)];
        for(int i=3;i<=N-1;i++)dp1[getid(i,M-1)]=a[getid(i,M-1)]+a[getid(i-1,M)];
        for(int i=3;i<=N-1;i++)
        {
            for(int j=2;j<=M-1;j++)
                dp1[getid(i,j)]=max(dp1[getid(i-1,j+1)],a[getid(i-1,j+1)])+a[getid(i,j)];
        }

        for(int j=2;j<=M-1;j++)dp2[getid(N-1,j)]=a[getid(N-1,j)]+a[getid(N,j-1)];
        for(int i=2;i<=N-2;i++)dp2[getid(i,2)]=a[getid(i,2)]+a[getid(i+1,1)];
        for(int i=N-2;i>=2;i--)
        {
            for(int j=3;j<=M-1;j++)
                dp2[getid(i,j)]=max(dp2[getid(i+1,j-1)],a[getid(i+1,j-1)])+a[getid(i,j)];
        }

        for(int j=2;j<=M-1;j++)dp3[getid(2,j)]=a[getid(2,j)]+a[getid(1,j-1)];
        for(int i=3;i<=N-1;i++)dp3[getid(i,2)]=a[getid(i,2)]+a[getid(i-1,1)];
        for(int i=3;i<=N-1;i++)
        {
            for(int j=3;j<=M-1;j++)
                dp3[getid(i,j)]=max(dp3[getid(i-1,j-1)],a[getid(i-1,j-1)])+a[getid(i,j)];
        }

        for(int j=2;j<=M-1;j++)dp4[getid(N-1,j)]=a[getid(N-1,j)]+a[getid(N,j+1)];
        for(int i=2;i<=N-2;i++)dp4[getid(i,M-1)]=a[getid(i,M-1)]+a[getid(i+1,M)];
        for(int i=N-2;i>=2;i--)
        {
            for(int j=2;j<=M-2;j++)
                dp4[getid(i,j)]=max(dp4[getid(i+1,j+1)],a[getid(i+1,j+1)])+a[getid(i,j)];
        }


        LL ans=0;
        for(int i=2;i<=N-1;i++)
        {
            for(int j=2;j<=M-1;j++)
            {
                int id=getid(i,j);
                ans=max(ans,dp1[id]+dp2[id]+dp3[id]+dp4[id]-3*a[id]);
            }
        }
        printf("Case #%d: %lld\n",cas++,ans);
    }
    return 0;
}







/*
4 5
1 2 3 4 5
6 7 8 9 0
0 9 8 7 6
5 4 3 2 1

3 3
1 2 3
4 5 6
7 8 9


*/

信息

递交者
类型
递交
语言
C++
递交时间
2019-06-09 23:59:23
评测时间
2019-06-09 23:59:23
评测机
分数
10
总耗时
957ms
峰值内存
38.41 MiB