Submission #775037

#	Time	Username	Problem	Language	Result	Execution time	Memory
775037		vjudge1	T-Covering (eJOI19_covering)	C++17	0 / 100	1089 ms	8668 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 1000005
ll int arr[N],dolu[N],dp[N],centr[N];
int n,m,k;
ll int hmm(int ama){
	if(ama>k)return 0;
	ll int a=-1000000000000;
	int orta=centr[ama];
	if(orta-m>0&&dolu[orta-m]==0){
		int xxx=arr[orta-m];
		if((orta-1)%m&&orta%m&&dolu[orta-1]+dolu[orta+1]==0){
			dolu[orta-m]=dolu[orta-1]=dolu[orta+1]=1;
			a=max(a,hmm(ama+1)+arr[orta-1]+xxx+arr[orta+1]);

			dolu[orta-m]=dolu[orta-1]=dolu[orta+1]=0;
		}
		if((orta-1)%m&&orta+m<=n*m&&dolu[orta-1]+dolu[orta+m]==0){

			dolu[orta-m]=dolu[orta-1]=dolu[orta+m]=1;
			a=max(a,hmm(ama+1)+xxx+arr[orta-1]+arr[orta+m]);
			dolu[orta-m]=dolu[orta-1]=dolu[orta+m]=0;
		}
		if(orta%m&&orta+m<=n*m&&dolu[orta+1]+dolu[orta+m]==0){
			dolu[orta-m]=dolu[orta+1]=dolu[orta+m]=1;
			a=max(a,hmm(ama+1)+xxx+arr[orta+1]+arr[orta+m]);
			dolu[orta-m]=dolu[orta+1]=dolu[orta+m]=0;
		}
	}
	if(orta%m&&(orta-1)%m&&orta+m<=n*m&&dolu[orta+1]+dolu[orta-1]+dolu[orta+m]==0){
		dolu[orta+m]=dolu[orta-1]=dolu[orta+1]=1;
		a=max(a,hmm(ama+1)+arr[orta-1]+arr[orta+m]+arr[orta+1]);
		dolu[orta+m]=dolu[orta-1]=dolu[orta+1]=0;
	}
	//cout<<orta<<" "<<a<<endl;
	return a;

}
int main(){
	lalala;
	memset(dp,-1,sizeof(dp));
	cin>>n>>m;
	ll int cev=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x;cin>>x;
			arr[(i*m)+j]=x;
			dp[(i*m)+j]=-1;
		}
	}
	cin>>k;
	for(int i=1;i<=k;i++){
		int x,y;cin>>x>>y;
		x++;y++;
		centr[i]=(x*m)+y;
		dolu[(x*m)+y]=1;
		cev+=arr[(x*m)+y];
	}
	ll int x=hmm(1);
	if(x>=0)cout<<x+cev<<endl;
	else cout<<"No"<<endl;


}

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