oj.uz

Submission #66991

# Submission time Handle Problem Language Result Execution time Memory
66991 2018-08-13T07:35:11 Z yusufake Maxcomp (info1cup18_maxcomp) C++
15 / 100
 3 ms 512 KB 
#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;

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

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

int main(){
    scanf("%d%d",&m,&n);
    memset(F , 22 , sizeof F);
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++){
            scanf("%d",&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 << ans; return 0;
    memset(F , 22 , 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 , 22 , 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 , 22 , 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("%d",ans-1);    
  return 0;
}

Compilation message

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("%d%d",&m,&n);
     ~~~~~^~~~~~~~~~~~~~
maxcomp.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Incorrect 3 ms 484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Incorrect 3 ms 484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Incorrect 3 ms 484 KB Output isn't correct
4 Halted 0 ms 0 KB -