제출 #407101

#제출 시각아이디문제언어결과실행 시간메모리
407101victoriadMaxcomp (info1cup18_maxcomp)C++14
0 / 100
1 ms332 KiB
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <utility> #include <queue> #include <map> #include <array> #include <iomanip> #include <fstream> #include <cstdlib> using namespace std; vector<vector<int> >A; vector<int>a; vector<int>b; vector<vector<int> >val; vector<vector<int> >lo; vector<vector<int> >hi; int ans; int m,n; void actualizar(vector<vector<pair<int,int> > >&con,int a,int b,vector<bool>&vi){ vi[a*m+b]=true; for(pair<int,int> c:con[a*m+b]){ int x=c.first; int y=c.second; if(!vi[x*m+y]){ int h=max(A[x][y],hi[a][b]); int l=min(A[x][y],lo[a][b]); int v=val[a][b]-hi[a][b]+lo[a][b]+h-l; if(v>val[x][y]){ ans=max(ans,v); val[x][y]=v; lo[x][y]=l; hi[x][y]=h; actualizar(con,x,y,vi); } } } } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int n,m; cin>>n>>m; A.resize(n); a.assign(m,-1); val.resize(n); lo.resize(n); hi.resize(n); for(int i=0;i<n;i++){ val[i]=a; hi[i]=a; lo[i]=a; } for(int i=0;i<n;i++)A[i]=a; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>A[i][j]; hi[i][j]=A[i][j]; lo[i][j]=A[i][j]; } } ans=-1; vector<vector<pair<int,int> > >con(n*m); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(i!=0){ int v=val[i-1][j]-hi[i-1][j]+lo[i-1][j]-1; int h=max(A[i][j],hi[i-1][j]); int l=min(A[i][j],lo[i-1][j]); v+=h; v-=l; if(v>val[i][j]){ val[i][j]=v; hi[i][j]=h; lo[i][j]=l; con[i*m+j].push_back(make_pair(i-1,j)); } if(v>val[i-1][j]){ val[i-1][j]=v; hi[i-1][j]=h; lo[i-1][j]=l; con[(i-1)*m+j].push_back(make_pair(i,j)); vector<bool>vi(n*m,false); actualizar(con,i-1,j,vi); } h=max(A[i][j],A[i-1][j]); l=min(A[i][j],A[i-1][j]); v=h-l-2; if(v>val[i][j]){ val[i][j]=v; hi[i][j]=h; lo[i][j]=l; con[i*m+j].push_back(make_pair(i-1,j)); } if(v>val[i-1][j]){ val[i-1][j]=v; hi[i-1][j]=h; lo[i-1][j]=l; con[(i-1)*m+j].push_back(make_pair(i,j)); vector<bool>vi(n*m,false); actualizar(con,i-1,j,vi); } } if(j!=0){ int v=val[i][j-1]-hi[i][j-1]+lo[i][j-1]-1; int h=max(A[i][j],hi[i][j-1]); int l=min(A[i][j],lo[i][j-1]); v+=h; v-=l; if(v>val[i][j]){ val[i][j]=v; hi[i][j]=h; lo[i][j]=l; con[i*m+j].push_back(make_pair(i,j-1)); } if(v>val[i][j-1]){ val[i][j-1]=v; hi[i][j-1]=h; lo[i][j-1]=l; con[(i)*m+j-1].push_back(make_pair(i,j)); vector<bool>vi(n*m,false); actualizar(con,i,j-1,vi); } h=max(A[i][j],A[i][j-1]); l=min(A[i][j],A[i][j-1]); v=h-l-2; if(v>val[i][j]){ val[i][j]=v; hi[i][j]=h; lo[i][j]=l; con[i*m+j].push_back(make_pair(i,j-1)); } if(v>val[i][j-1]){ val[i][j-1]=v; hi[i][j-1]=h; lo[i][j-1]=l; con[(i)*m+j-1].push_back(make_pair(i,j)); vector<bool>vi(n*m,false); actualizar(con,i,j-1,vi); } } ans=max(ans,val[i][j]); } } for(int i=n-1;i>0;i--){ for(int j=m-1;j>0;j--){ if(i!=n-1){ int v=val[i+1][j]-hi[i+1][j]+lo[i+1][j]-1; int h=max(A[i][j],hi[i+1][j]); int l=min(A[i][j],lo[i+1][j]); v+=h; v-=l; if(v>val[i][j]){ val[i][j]=v; hi[i][j]=h; lo[i][j]=l; con[i*m+j].push_back(make_pair(i+1,j)); } if(v>val[i+1][j]){ val[i+1][j]=v; hi[i+1][j]=h; lo[i+1][j]=l; con[(i+1)*m+j].push_back(make_pair(i,j)); vector<bool>vi(n*m,false); actualizar(con,i+1,j,vi); } h=max(A[i][j],A[i+1][j]); l=min(A[i][j],A[i+1][j]); v=h-l-2; if(v>val[i][j]){ val[i][j]=v; hi[i][j]=h; lo[i][j]=l; con[i*m+j].push_back(make_pair(i+1,j)); } if(v>val[i+1][j]){ val[i+1][j]=v; hi[i+1][j]=h; lo[i+1][j]=l; con[(i+1)*m+j].push_back(make_pair(i,j)); vector<bool>vi(n*m,false); actualizar(con,i+1,j,vi); } } if(j!=m-1){ int v=val[i][j+1]-hi[i][j+1]+lo[i][j+1]-1; int h=max(A[i][j],hi[i][j+1]); int l=min(A[i][j],lo[i][j+1]); v+=h; v-=l; if(v>val[i][j]){ val[i][j]=v; hi[i][j]=h; lo[i][j]=l; con[i*m+j].push_back(make_pair(i,j+1)); } if(v>val[i][j+1]){ val[i][j+1]=v; hi[i][j+1]=h; lo[i][j+1]=l; con[(i)*m+j+1].push_back(make_pair(i,j)); vector<bool>vi(n*m,false); actualizar(con,i,j+1,vi); } h=max(A[i][j],A[i][j+1]); l=min(A[i][j],A[i][j+1]); v=h-l-2; if(v>val[i][j]){ val[i][j]=v; hi[i][j]=h; lo[i][j]=l; con[i*m+j].push_back(make_pair(i,j+1)); } if(v>val[i][j+1]){ val[i][j+1]=v; hi[i][j+1]=h; lo[i][j+1]=l; con[(i)*m+j+1].push_back(make_pair(i,j)); vector<bool>vi(n*m,false); actualizar(con,i,j+1,vi); } } ans=max(ans,val[i][j]); } } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...