oj.uz

Submission #486112

# Submission time Handle Problem Language Result Execution time Memory
486112 2021-11-10T14:48:36 Z leaked Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 154 ms 39544 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=-1,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:16: warning: unused variable 'rans' [-Wunused-variable]
   75 |     int ans=-1,rans=-inf;
      |                ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31692 KB Output is correct
2 Correct 14 ms 31592 KB Output is correct
3 Correct 14 ms 31564 KB Output is correct
4 Correct 14 ms 31608 KB Output is correct
5 Correct 15 ms 31564 KB Output is correct
6 Correct 14 ms 31648 KB Output is correct
7 Correct 16 ms 31672 KB Output is correct
8 Correct 16 ms 31656 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31692 KB Output is correct
2 Correct 14 ms 31692 KB Output is correct
3 Correct 13 ms 31692 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31692 KB Output is correct
2 Correct 14 ms 31592 KB Output is correct
3 Correct 14 ms 31564 KB Output is correct
4 Correct 14 ms 31608 KB Output is correct
5 Correct 15 ms 31564 KB Output is correct
6 Correct 14 ms 31648 KB Output is correct
7 Correct 16 ms 31672 KB Output is correct
8 Correct 16 ms 31656 KB Output is correct
9 Correct 14 ms 31604 KB Output is correct
10 Correct 14 ms 31644 KB Output is correct
11 Correct 14 ms 31680 KB Output is correct
12 Correct 18 ms 31708 KB Output is correct
13 Correct 14 ms 31692 KB Output is correct
14 Correct 14 ms 31644 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31692 KB Output is correct
2 Correct 14 ms 31592 KB Output is correct
3 Correct 14 ms 31564 KB Output is correct
4 Correct 14 ms 31608 KB Output is correct
5 Correct 15 ms 31564 KB Output is correct
6 Correct 14 ms 31648 KB Output is correct
7 Correct 16 ms 31672 KB Output is correct
8 Correct 16 ms 31656 KB Output is correct
9 Correct 18 ms 31692 KB Output is correct
10 Correct 14 ms 31692 KB Output is correct
11 Correct 13 ms 31692 KB Output is correct
12 Correct 14 ms 31604 KB Output is correct
13 Correct 14 ms 31644 KB Output is correct
14 Correct 14 ms 31680 KB Output is correct
15 Correct 18 ms 31708 KB Output is correct
16 Correct 14 ms 31692 KB Output is correct
17 Correct 14 ms 31644 KB Output is correct
18 Correct 131 ms 39544 KB Output is correct
19 Correct 118 ms 39448 KB Output is correct
20 Correct 112 ms 39080 KB Output is correct
21 Correct 125 ms 39500 KB Output is correct
22 Correct 154 ms 39540 KB Output is correct
23 Correct 131 ms 39540 KB Output is correct
24 Correct 111 ms 39148 KB Output is correct