Submission #66997

#	Time	Username	Problem	Language	Result	Execution time	Memory
66997		yusufake	Maxcomp (info1cup18_maxcomp)	C++98	100 / 100	330 ms	8560 KiB

maxcomp

#include<bits/stdc++.h>
using namespace std;

#define _   int v, int tl, int tr, int l, int r, pp x
#define tm  (tl + tr >> 1)
#define sol v,tl,tm,l,r,x
#define sag v,tm+1,tr,l,r,x

#define mp make_pair
#define pb push_back
#define st first
#define nd second

typedef long long ll;
typedef pair < int , int > pp;
typedef vector < int > vi;

const int mod = 1e9 + 7;
const int N   = 1e3 + 3;

ll F[N],A[N][N],n,m,i,j,t,ans;

void up(int x, ll t){
    for(; x <= n ; x += x&-x) 
        F[x] = min(F[x] , t);
}
ll qry(int x){
    ll t=1LL<<55;
    for(; x ; x -= x&-x)
        t = min(t , F[x]);
    return t;
}

int main(){
    scanf("%lld%lld",&m,&n);
    memset(F , 127 , sizeof F);
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++){
            scanf("%lld",&A[i][j]);
            t = A[i][j] - i - j;
            up(j,t);
            ans = max(ans , t-qry(j));
         //   cout << i << " " << j << " " << t << " " << ans << " aa\n";
        }    
    //cout << F[n+1]; return 0;
    memset(F , 127 , sizeof F);
    for(i=1;i<=m;i++)
        for(j=n; j ;j--){
            t = A[i][j] - i + j;
            up(n-j+1,t);
            ans = max(ans , t-qry(n-j+1));
        }    
    memset(F , 127 , sizeof F);
    for(i=m; i ;i--)
        for(j=1;j<=n;j++){
            t = A[i][j] + i - j;
            up(j,t);
            ans = max(ans , t-qry(j));
        }    
    memset(F , 127 , sizeof F);
    for(i=m; i ;i--)
        for(j=n; j ;j--){
            t = A[i][j] + i + j;
            up(n-j+1,t);
            ans = max(ans , t-qry(n-j+1));
        }    
    
    printf("%lld",ans-1);    
  return 0;
}

Compilation message (stderr)

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&m,&n);
     ~~~~~^~~~~~~~~~~~~~~~~~
maxcomp.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld",&A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40