oj.uz

답안 #486108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
486108 2021-11-10T14:47:13 Z leaked Maxcomp (info1cup18_maxcomp) C++14
60 / 100
 500 ms 42860 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=0,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<<rans;
    return 0;
}
/*
2 3
7 4 3
5 2 5
*/

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 31688 KB Output is correct
2 Correct 15 ms 31564 KB Output is correct
3 Correct 14 ms 31692 KB Output is correct
4 Correct 14 ms 31688 KB Output is correct
5 Correct 14 ms 31664 KB Output is correct
6 Correct 15 ms 31588 KB Output is correct
7 Correct 19 ms 31564 KB Output is correct
8 Correct 15 ms 31692 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31692 KB Output is correct
2 Correct 17 ms 31692 KB Output is correct
3 Correct 18 ms 31664 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 31688 KB Output is correct
2 Correct 15 ms 31564 KB Output is correct
3 Correct 14 ms 31692 KB Output is correct
4 Correct 14 ms 31688 KB Output is correct
5 Correct 14 ms 31664 KB Output is correct
6 Correct 15 ms 31588 KB Output is correct
7 Correct 19 ms 31564 KB Output is correct
8 Correct 15 ms 31692 KB Output is correct
9 Correct 36 ms 31692 KB Output is correct
10 Correct 31 ms 31692 KB Output is correct
11 Correct 31 ms 31692 KB Output is correct
12 Correct 33 ms 31632 KB Output is correct
13 Correct 35 ms 31732 KB Output is correct
14 Correct 41 ms 31720 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 31688 KB Output is correct
2 Correct 15 ms 31564 KB Output is correct
3 Correct 14 ms 31692 KB Output is correct
4 Correct 14 ms 31688 KB Output is correct
5 Correct 14 ms 31664 KB Output is correct
6 Correct 15 ms 31588 KB Output is correct
7 Correct 19 ms 31564 KB Output is correct
8 Correct 15 ms 31692 KB Output is correct
9 Correct 17 ms 31692 KB Output is correct
10 Correct 17 ms 31692 KB Output is correct
11 Correct 18 ms 31664 KB Output is correct
12 Correct 36 ms 31692 KB Output is correct
13 Correct 31 ms 31692 KB Output is correct
14 Correct 31 ms 31692 KB Output is correct
15 Correct 33 ms 31632 KB Output is correct
16 Correct 35 ms 31732 KB Output is correct
17 Correct 41 ms 31720 KB Output is correct
18 Execution timed out 1064 ms 42860 KB Time limit exceeded
19 Halted 0 ms 0 KB -