Submission #486096

#	Time	Username	Problem	Language	Result	Execution time	Memory
486096		leaked	Maxcomp (info1cup18_maxcomp)	C++14	15 / 100	13 ms	15976 KiB

maxcomp

#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);

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=1e9;
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=-1;
    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);
        }
    }
    cout<<ans;
    return 0;
}

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