Submission #1174444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174444		guagua0407	Maxcomp (info1cup18_maxcomp)	C++20	60 / 100	481 ms	4832 KiB

maxcomp

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=1e3+5;
const ll inf=(ll)1e18;
vector<vector<ll>> st(mxn*4,vector<ll>(2,-inf));

void update(int id,int pos,ll val,int l=0,int r=mxn-1,int v=1){
    if(l==r){
        st[v][id]=max(st[v][id],val);
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(id,pos,val,l,mid,v*2);
    else update(id,pos,val,mid+1,r,v*2+1);
    st[v][id]=max(st[v*2][id],st[v*2+1][id]);
}

ll query(int id,int tl,int tr,int l=0,int r=mxn-1,int v=1){
    if(r<tl or tr<l){
        return -inf;
    }
    if(tl<=l and r<=tr){
        return st[v][id];
    }
    int mid=(l+r)/2;
    return max(query(id,tl,min(mid,tr),l,mid,v*2),query(id,max(mid+1,tl),tr,mid+1,r,v*2+1));
}

int main() {_
    auto stt=clock();
    int n,m;
    cin>>n>>m;
    vector<vector<int>> a(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    ll ans=-1;
    auto go=[&](){
        st=vector<vector<ll>>(mxn*4,vector<ll>(2,-inf));
        for(int j=0;j<m and (clock()-stt)<0.48*CLOCKS_PER_SEC;j++){
            for(int i=0;i<n;i++){
                update(0,i,-a[i][j]+i+j);
                update(1,i,-a[i][j]-i+j);
            }
            for(int i=0;i<n;i++){
                //cout<<a[i][j]<<' '<<query(0,0,i)<<' '<<query(1,i,n-1)<<'\n';
                ans=max({ans,a[i][j]-i-j+query(0,0,i)-1,a[i][j]+i-j+query(1,i,n-1)-1});
            }
        }
    };
    for(int t=0;t<2;t++){
        go();
        for(int i=0;i<n;i++){
            reverse(all(a[i]));
        }
    }
    cout<<ans<<'\n';
    return 0;
}
//maybe its multiset not set
//yeeorz
//diaoborz

Compilation message (stderr)

maxcomp.cpp: In function 'void setIO(std::string)':
maxcomp.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
maxcomp.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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