Submission #775564

#	Time	Username	Problem	Language	Result	Execution time	Memory
775564		DangerNoodle7591	T-Covering (eJOI19_covering)	C++17	30 / 100	55 ms	20124 KiB

covering

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

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30