oj.uz

Submission #923305

# Submission time Handle Problem Language Result Execution time Memory
923305 2024-02-07T05:37:45 Z vjudge1 Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 133 ms 25168 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define int ll
#define y1 yy
#define maksim gay
#define ppb pop_back
#define gcd(a,b) __gcd(a,b)
#define in insert

const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};

const int inf=1e16;
const int N=5e4+100;
const int MAX=1010;
const int mod=1e9+7;


int n,m;
int a[MAX][MAX];
int mn[MAX][MAX];

void solve(){
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>a[i][j];
    }
  }
  int ans=-inf;
  {
    for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++){
      mn[i][j]=-inf;
    }
    for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
        mn[i][j]=max(mn[i-1][j],mn[i][j-1]);
        mn[i][j]=max(mn[i][j],-a[i][j]+i+j-1);
        ans=max(ans,a[i][j]+mn[i][j]-i-j);
      }
    }
  }
  {
    for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++){
      mn[i][j]=-inf;
    }
    for(int i=1;i<=n;i++){
      for(int j=m;j>=1;j--){
        mn[i][j]=max(mn[i-1][j],mn[i][j+1]);
        mn[i][j]=max(mn[i][j],-a[i][j]+i-j-1);
        ans=max(ans,a[i][j]+mn[i][j]-i+j);
      }
    }
  }
  {
    for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++){
      mn[i][j]=-inf;
    }
    for(int i=n;i>=1;i--){
      for(int j=1;j<=m;j++){
        mn[i][j]=max(mn[i+1][j],mn[i][j-1]);
        mn[i][j]=max(mn[i][j],-a[i][j]-i+j-1);
        ans=max(ans,a[i][j]+mn[i][j]+i-j);
      }
    }    
  }
  {
    for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++){
      mn[i][j]=-inf;
    }
    for(int i=n;i>=1;i--){
      for(int j=m;j>=1;j--){
        mn[i][j]=max(mn[i+1][j],mn[i][j+1]);
        mn[i][j]=max(mn[i][j],-a[i][j]-i-j-1);
        // cout<<i<<" "<<j<<" "<<a[i][j]<<" "<<mn[i][j]<<"\n";
        ans=max(ans,a[i][j]+mn[i][j]+i+j);
      }
    }        
  }
  cout<<ans<<"\n";
}

main(){
  // freopen("prizes.in", "r", stdin);
  // freopen("prizes.out", "w", stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message

maxcomp.cpp:98:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   98 | main(){
      | ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2512 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2512 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4696 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2512 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 2 ms 4444 KB Output is correct
14 Correct 1 ms 4696 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4696 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 133 ms 24936 KB Output is correct
19 Correct 116 ms 24656 KB Output is correct
20 Correct 107 ms 24516 KB Output is correct
21 Correct 130 ms 24644 KB Output is correct
22 Correct 117 ms 24656 KB Output is correct
23 Correct 116 ms 24856 KB Output is correct
24 Correct 108 ms 25168 KB Output is correct