/ tabris /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 2ms 2.324 MiB
#2 Accepted 2ms 2.211 MiB
#3 Accepted 280ms 39.664 MiB
#4 Accepted 304ms 25.516 MiB
#5 Accepted 278ms 35.074 MiB

代码

#include<bits/stdc++.h>
using namespace std;
#define fe(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
int n,m;
const int N= 2e6+5;
int Hash(int x,int y){
    return x*(m+2) + y+2;
}
ll a[N];
ll dp[N][4];
int main(){
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int kase=1;
    while(~scanf("%d%d",&n,&m)){
        fe(i,1,n)
            fe(j,1,m)
                scanf("%lld",&a[Hash(i,j)]);
        fe(i,0,n+1)
            fe(j,0,m+1)
                fe(k,0,3)
                    dp[Hash(i,j)][k]=-1e18;
        fe(i,1,n)
            fe(j,1,m)
                dp[Hash(i,j)][0] = max(a[Hash(i,j)],dp[Hash(i-1,j-1)][0]+a[Hash(i,j)]);
        for(int i=1;i<=n;i++)
            for(int j=m;j;j--)
                dp[Hash(i,j)][1] = max(a[Hash(i,j)],dp[Hash(i-1,j+1)][1]+a[Hash(i,j)]);
        for(int i=n;i;i--)
            fe(j,1,m)
                dp[Hash(i,j)][2] = max(a[Hash(i,j)],dp[Hash(i+1,j-1)][2]+a[Hash(i,j)]);
        for(int i=n;i;i--)
            for(int j=m;j;j--)
                dp[Hash(i,j)][3] = max(a[Hash(i,j)],dp[Hash(i+1,j+1)][3]+a[Hash(i,j)]);
        ll ans = -1e18;

        fe(i,2,n-1)
            fe(j,2,m-1){
                ll now = dp[Hash(i-1,j-1)][0]+dp[Hash(i-1,j+1)][1]
                    +dp[Hash(i+1,j-1)][2]+dp[Hash(i+1,j+1)][3]+a[Hash(i,j)];
                ans =max(ans,now);
            }
        printf("Case #%d: %lld\n",kase++,ans);

    }

    return 0;
}

信息

递交者
类型
递交
语言
C++
递交时间
2019-06-12 20:53:48
评测时间
2019-06-12 20:53:48
评测机
分数
50
总耗时
867ms
峰值内存
39.664 MiB