Submission #1051238

#TimeUsernameProblemLanguageResultExecution timeMemory
1051238pccMaxcomp (info1cup18_maxcomp)C++17
100 / 100
64 ms17496 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int inf = 1e9; const int mxn = 1010; int arr[mxn][mxn]; int dp[mxn][mxn]; int N,M; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N>>M; for(auto &i:arr)for(auto &j:i)j = -inf*2; for(auto &i:dp)for(auto &j:i)j = -inf*2; for(int i = 1;i<=N;i++){ for(int j = 1;j<=M;j++)cin>>arr[i][j]; } int ans = -inf*2; for(int i = 1;i<=N;i++){ for(int j = 1;j<=M;j++){ dp[i][j] = max(dp[i-1][j],dp[i][j-1]); dp[i][j] = max(dp[i][j],-arr[i][j]+i+j); ans = max(ans,dp[i][j]-i-j+arr[i][j]-1); } } for(int i = N;i>=1;i--){ for(int j = 1;j<=M;j++){ dp[i][j] = max(dp[i+1][j],dp[i][j-1]); dp[i][j] = max(dp[i][j],-arr[i][j]-i+j); ans = max(ans,dp[i][j]+i-j+arr[i][j]-1); } } for(int i = 1;i<=N;i++){ for(int j = M;j>=1;j--){ dp[i][j] = max(dp[i-1][j],dp[i][j+1]); dp[i][j] = max(dp[i][j],-arr[i][j]+i-j); ans = max(ans,dp[i][j]-i+j+arr[i][j]-1); } } for(int i = N;i>=1;i--){ for(int j = M;j>=1;j--){ dp[i][j] = max(dp[i+1][j],dp[i][j+1]); dp[i][j] = max(dp[i][j],-arr[i][j]-i-j); ans = max(ans,dp[i][j]+i+j+arr[i][j]-1); } } cout<<ans<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...