제출 #407101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407101		victoriad	Maxcomp (info1cup18_maxcomp)	C++14	0 / 100	1 ms	332 KiB

maxcomp

#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;
 }

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