Submission #1051270

#TimeUsernameProblemLanguageResultExecution timeMemory
105127012345678Maxcomp (info1cup18_maxcomp)C++17
100 / 100
244 ms16012 KiB
#include <bits/stdc++.h> using namespace std; const int nx=1505; int n, m, a[nx][nx], res=INT_MIN; struct segtree { int d[4*nx]; void build(int l, int r, int i) { d[i]=-2e9; if (l==r) return; int md=(l+r)/2; build(l, md, 2*i); build(md+1, r, 2*i+1); } void update(int l, int r, int i, int idx, int vl) { if (idx<l||r<idx) return; if (l==r) return d[i]=max(d[i], vl), void(); int md=(l+r)/2; update(l, md, 2*i, idx, vl); update(md+1, r, 2*i+1, idx, vl); d[i]=max(d[2*i], d[2*i+1]); } int query(int l, int r, int i, int ql, int qr) { if (qr<l||r<ql) return INT_MIN; if (ql<=l&&r<=qr) return d[i]; int md=(l+r)/2; return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr)); } } up, dn; int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>a[i][j]; up.build(1, m, 1); dn.build(1, m, 1); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { up.update(1, m, 1, j, -a[i][j]+j+i); //cout<<"query up "<<i<<' '<<j<<' '<<a[i][j]+i+j+up.query(1, n, 1, 1, j)-1<<'\n'; res=max(res, a[i][j]-i-j+up.query(1, m, 1, 1, j)-1); } for (int j=m; j>=1; j--) { dn.update(1, m, 1, j, -a[i][j]-j+i); res=max(res, a[i][j]-i+j+dn.query(1, m, 1, j, m)-1); } } up.build(1, m, 1); dn.build(1, m, 1); for (int i=n; i>=1; i--) { for (int j=1; j<=m; j++) { up.update(1, m, 1, j, -a[i][j]+j-i); res=max(res, a[i][j]+i-j+up.query(1, m, 1, 1, j)-1); } for (int j=m; j>=1; j--) { dn.update(1, m, 1, j, -a[i][j]-j-i); res=max(res, a[i][j]+i+j+dn.query(1, m, 1, j, m)-1); } } cout<<res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...