이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"
#define ll long long
#define pb push_back
#define N 2000000
int k,n,m;
ll int off[N],alan[N];
int arr[N][2];
ll int hmm(int yer){
if(yer>=k)return 0;
ll int cev=-1000000000000;
int a=arr[yer][0],b=arr[yer][1];
b++;
int konum=(a*m)+b;
if(konum+m<=n*m&&konum-m>0&&alan[konum+m]==0&&alan[konum-m]==0){
if((konum-1)%m&&konum>1&&alan[konum-1]==0){
alan[konum+m]=alan[konum-m]=alan[konum-1]=1;
cev=max(cev,off[konum+m]+off[konum-m]+off[konum-1]+off[konum]+hmm(yer+1));
alan[konum+m]=alan[konum-m]=alan[konum-1]=0;
//cout<<yer<<" a "<<cev<<" "<<konum<<endl;
}
if(konum%m&&alan[konum+1]==0){
alan[konum+m]=alan[konum-m]=alan[konum+1]=1;
cev=max(cev,off[konum+m]+off[konum-m]+off[konum+1]+off[konum]+hmm(yer+1));
alan[konum+m]=alan[konum-m]=alan[konum+1]=0;
//cout<<yer<<" b "<<cev<<" "<<konum<<endl;
}
}
if((konum-1)%m&&konum>1&&konum%m&&alan[konum-1]==0&&alan[konum+1]==0){
if(konum+m<=n*m&&alan[konum+m]==0){
alan[konum+m]=alan[konum+1]=alan[konum-1]=1;
cev=max(cev,off[konum+m]+off[konum+1]+off[konum-1]+off[konum]+hmm(yer+1));
alan[konum+m]=alan[konum+1]=alan[konum-1]=0;
//cout<<yer<<" c "<<cev<<" "<<konum<<endl;
}
if(konum-m>0&&alan[konum-m]==0){
alan[konum-m]=alan[konum+1]=alan[konum-1]=1;
cev=max(cev,off[konum-m]+off[konum+1]+off[konum-1]+off[konum]+hmm(yer+1));
alan[konum-m]=alan[konum+1]=alan[konum-1]=0;
//cout<<yer<<" d "<<cev<<" "<<konum<<endl;
}
}
//cout<<yer<<"_"<<cev<<" "<<konum<<endl;
return cev;
}
map<pair<int,int>,int> mp;
int main(){
lalala;
cin>>n>>m;
int mat[n][m];
int yap[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mat[i][j];
off[i*m+j+1]=mat[i][j];
yap[i][j]=0;
}
}
cin>>k;
ll int cev=0;
int yes=1;
for(int i=0;i<k;i++){
cin>>arr[i][0]>>arr[i][1];
alan[arr[i][0]*m+arr[i][1]+1]=1;
if(mp[{arr[i][0],arr[i][1]}]){
yes=0;
}
mp[{arr[i][0],arr[i][1]}]=1;
}
if(yes==0){
cout<<"No"<<endl;
return 0;
}
if(k<=10){
cev=hmm(0);
if(cev>-1)cout<<cev<<endl;
else cout<<"No"<<endl;
return 0;
}
for(int i=0;i<k&&yes;i++){
int a=arr[i][0], b=arr[i][1];
int kac=0,toplam=0;
cev+=mat[a][b];
if(mp[{a+1,b}]){
kac++;
if(a+2>=n||a-1<0||b+1>=m||b-1<0){yes=0;break;}
toplam=(mat[a-1][b]+mat[a+2][b]+mat[a][b-1]+mat[a][b+1]+mat[a+1][b-1]+mat[a+1][b+1]);
yap[a+1][b]=1; }
if(mp[{a-1,b}]){
kac++;
if(a+1>=n||a-2<0||b+1>=m||b-1<0){yes=0;break;}
toplam=(mat[a+1][b]+mat[a-2][b]+mat[a][b-1]+mat[a][b+1]+mat[a-1][b-1]+mat[a-1][b+1]);
yap[a-1][b]=1;
}
if(mp[{a,b+1}]){
kac++;
if(a+1>=n||a-1<0||b+2>=m||b-1<0){yes=0;break;}
toplam=(mat[a+1][b]+mat[a-1][b]+mat[a][b-1]+mat[a][b+2]+mat[a-1][b+1]+mat[a+1][b+1]);
yap[a][b+1]=1;
}
if(mp[{a,b-1}]){
kac++;
if(a+1>=n||a-1<0||b+1>=m||b-2<0){yes=0;break;}
toplam=(mat[a+1][b]+mat[a-1][b]+mat[a][b+1]+mat[a][b-2]+mat[a-1][b-1]+mat[a+1][b-1]);
yap[a][b-1]=1;
}
if(kac){
if(kac>1){yes=0;break;}
//cout<<toplam<<endl;
if(yap[a][b]==0)cev+=toplam;
continue;
}
int aaa=0;
if(a+1<n&&a-1>-1){
if(b+1<m)aaa=max(aaa,mat[a+1][b]+mat[a-1][b]+mat[a][b+1]);
if(b-1>-1)aaa=max(aaa,mat[a+1][b]+mat[a-1][b]+mat[a][b-1]);
}
if(b+1<m&&b-1>-1){
if(a+1<n)aaa=max(aaa,mat[a+1][b]+mat[a][b-1]+mat[a][b+1]);
if(a-1>-1)aaa=max(aaa,mat[a][b+1]+mat[a-1][b]+mat[a][b-1]);
}
//cout<<a<<" "<<b<<aaa<<endl;
if(yap[a][b]==0)cev+=aaa;
yap[a][b]=1;
if(aaa==0){yes=0;break;}
}
if(yes)cout<<cev<<endl;
else cout<<"No"<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |