oj.uz

Submission #486111

# Submission time Handle Problem Language Result Execution time Memory
486111 2021-11-10T14:48:07 Z leaked Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 148 ms 47096 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define vec vector
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m_p make_pair
#define pw(x) (1LL<<x)
#define pb push_back
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;

template<class T> bool umin(T &a, const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a, const T &b){return (a<b?a=b,1:0);}

const int N=1e3+1;
const int inf=1e18;
struct prefx{
    int sx,sy,ex,ey,dx,dy;
    int mx[N][N];
    prefx(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++)
                mx[i][j]=-inf;
        }
    }
    void _init(int _sx,int _sy,int _dx,int _dy,int _ex,int _ey){
        ex=_ex;
        sx=_sx;
        ey=_ey;
        sy=_sy;
        dx=_dx;dy=_dy;
    }
    void _set(int i,int j,int x){
        umax(mx[i][j],x);
    }
    void build(){
        for(int i=sx;i!=ex;i+=dx){
            for(int j=sy;j!=ey;j+=dy){
//                cout<<i<<' '<<j<<endl;
                umax(mx[i][j],(i-dx>=0 && i-dx<N?mx[i-dx][j]:-inf));
            }
        }
        for(int i=sx;i!=ex;i+=dx){
            for(int j=sy;j!=ey;j+=dy){
                umax(mx[i][j],(j-dy>=0 && j-dy<N?mx[i][j-dy]:-inf));
//                cout<<i<<' '<<j<<' '<<mx[i][j]<<endl;
            }
//            cout<<endl;
        }
//        for(int i=sx;i!=i)
    }
}pref[4];
signed main(){
    fast_rmi;
    int n,m;
    cin>>n>>m;
    pref[0]._init(0,0,1,1,n,m);
    pref[1]._init(n-1,0,-1,1,-1,m);
    pref[2]._init(0,m-1,1,-1,n,-1);
    pref[3]._init(n-1,m-1,-1,-1,-1,-1);
    vec<vec<int>>a(n,vec<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            pref[0]._set(i,j,i+j-a[i][j]);
            pref[1]._set(i,j,-i+j-a[i][j]);
            pref[2]._set(i,j,+i-j-a[i][j]);
            pref[3]._set(i,j,-i-j-a[i][j]);
        }
    }
    for(int t=0;t<4;t++) cerr<<"BUILD "<<t<<endl,pref[t].build();
    int ans=-inf,rans=-inf;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            umax(ans,a[i][j]+pref[0].mx[i][j]-i-j-1);
            umax(ans,a[i][j]+pref[1].mx[i][j]+i-j-1);
            umax(ans,a[i][j]+pref[2].mx[i][j]-i+j-1);
            umax(ans,a[i][j]+pref[3].mx[i][j]+i+j-1);
//            for(int k=0;k<n;k++){
//                for(int t=0;t<m;t++){
//                    umax(rans,max(a[i][j],a[k][t])-min(a[i][j],a[k][t])-abs(i-k)-abs(j-t)-1);
//                }
//            }
        }
    }
    cout<<ans;
    return 0;
}
/*
2 3
7 4 3
5 2 5
*/

Compilation message

maxcomp.cpp: In function 'int main()':
maxcomp.cpp:75:18: warning: unused variable 'rans' [-Wunused-variable]
   75 |     int ans=-inf,rans=-inf;
      |                  ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31564 KB Output is correct
2 Correct 12 ms 31564 KB Output is correct
3 Correct 11 ms 31612 KB Output is correct
4 Correct 12 ms 31564 KB Output is correct
5 Correct 12 ms 31584 KB Output is correct
6 Correct 12 ms 31684 KB Output is correct
7 Correct 13 ms 31692 KB Output is correct
8 Correct 13 ms 31688 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31660 KB Output is correct
2 Correct 12 ms 31692 KB Output is correct
3 Correct 12 ms 31692 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31564 KB Output is correct
2 Correct 12 ms 31564 KB Output is correct
3 Correct 11 ms 31612 KB Output is correct
4 Correct 12 ms 31564 KB Output is correct
5 Correct 12 ms 31584 KB Output is correct
6 Correct 12 ms 31684 KB Output is correct
7 Correct 13 ms 31692 KB Output is correct
8 Correct 13 ms 31688 KB Output is correct
9 Correct 13 ms 31692 KB Output is correct
10 Correct 12 ms 31692 KB Output is correct
11 Correct 12 ms 31692 KB Output is correct
12 Correct 14 ms 31692 KB Output is correct
13 Correct 13 ms 31604 KB Output is correct
14 Correct 13 ms 31692 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31564 KB Output is correct
2 Correct 12 ms 31564 KB Output is correct
3 Correct 11 ms 31612 KB Output is correct
4 Correct 12 ms 31564 KB Output is correct
5 Correct 12 ms 31584 KB Output is correct
6 Correct 12 ms 31684 KB Output is correct
7 Correct 13 ms 31692 KB Output is correct
8 Correct 13 ms 31688 KB Output is correct
9 Correct 12 ms 31660 KB Output is correct
10 Correct 12 ms 31692 KB Output is correct
11 Correct 12 ms 31692 KB Output is correct
12 Correct 13 ms 31692 KB Output is correct
13 Correct 12 ms 31692 KB Output is correct
14 Correct 12 ms 31692 KB Output is correct
15 Correct 14 ms 31692 KB Output is correct
16 Correct 13 ms 31604 KB Output is correct
17 Correct 13 ms 31692 KB Output is correct
18 Correct 122 ms 39668 KB Output is correct
19 Correct 123 ms 46964 KB Output is correct
20 Correct 114 ms 46512 KB Output is correct
21 Correct 147 ms 46968 KB Output is correct
22 Correct 124 ms 47096 KB Output is correct
23 Correct 148 ms 46920 KB Output is correct
24 Correct 134 ms 46568 KB Output is correct