Submission #1280276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280276		akmuhammet_s	T-Covering (eJOI19_covering)	C++20	20 / 100	334 ms	8508 KiB

covering

#include "bits/stdc++.h"
using namespace std;
#define mod 998244353
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define N 24
#define maxn 200005

ll n,m,k;
vector<ll> a[maxn];
pair<ll,ll> p[maxn];

ll calc(ll qq){
	bool mm[n+5][m+5];
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) mm[i][j]=false;
	ll ans=0;
	for(ll i=1; i<=k; i++){
		ll x=p[i].ff,y=p[i].ss;
		if(qq%4==0){
			if(x==1 or y==1 or y==m) return -1;
			if(mm[x][y] or mm[x][y+1] or mm[x-1][y] or mm[x][y-1]) return -1;
			ans+=a[x][y]+a[x][y+1]+a[x-1][y]+a[x][y-1];
			mm[x][y]=mm[x][y+1]=mm[x-1][y]=mm[x][y-1]=true;
		}
		if(qq%4==1){
			if(x==1 or y==1 or x==n) return -1;
			if(mm[x][y] or mm[x+1][y] or mm[x-1][y] or mm[x][y-1]) return -1;
			ans+=a[x][y]+a[x+1][y]+a[x-1][y]+a[x][y-1];
			mm[x][y]=mm[x+1][y]=mm[x-1][y]=mm[x][y-1]=true;
		}
		if(qq%4==2){
			if(x==1 or y==m or x==n) return -1;
			if(mm[x][y] or mm[x+1][y] or mm[x][y+1] or mm[x-1][y]) return -1;
			ans+=a[x][y]+a[x+1][y]+a[x][y+1]+a[x-1][y];
			mm[x][y]=mm[x+1][y]=mm[x][y+1]=mm[x-1][y]=true;
		}
		if(qq%4==3){
			if(y==1 or y==m or x==n) return -1;
			if(mm[x][y] or mm[x+1][y] or mm[x][y+1] or mm[x][y-1]) return -1;
			ans+=a[x][y]+a[x+1][y]+a[x][y+1]+a[x][y-1];
			mm[x][y]=mm[x+1][y]=mm[x][y+1]=mm[x][y-1]=true;
		}
		qq/=4;
	}
	return ans;
}

void solve(){
	cin>>n>>m;
	for(ll i=1; i<=n; i++){
		a[i].pb(0ll);
		ll x;
		for(ll j=1; j<=m; j++){
			cin>>x;
			a[i].pb(x);
		}
	}
	cin>>k;
	for(ll i=1; i<=k; i++){
		cin>>p[i].ff>>p[i].ss;
		p[i].ff++;
		p[i].ss++;
	}
	if(k<=10){
		ll ans=-1,cnt=0;
		for(ll i=0; i<pow(4,k); i++){
			ll x=calc(i);
			ans=max(ans,x);
		}
		if(ans==-1) cout<<"No\n";
		else cout<<ans<<'\n';
		
		return;
	}
	ll sum=0ll;
	for(ll i=1; i<=k; i++){
		ll x=0ll;
		bool aa,b,c,d;
		aa=(p[i].ff>1);
		b=(p[i].ss>1);
		c=(p[i].ff<n);
		d=(p[i].ss<m);
		// p[i].ff++;
		// p[i].ss++;
		if(aa and b and d){
			x=max(x,a[p[i].ff][p[i].ss]+a[p[i].ff-1][p[i].ss]+a[p[i].ff][p[i].ss-1]+a[p[i].ff][p[i].ss+1]);
		}
		if(aa and c and d){
			x=max(x,a[p[i].ff][p[i].ss]+a[p[i].ff-1][p[i].ss]+a[p[i].ff+1][p[i].ss]+a[p[i].ff][p[i].ss+1]);
		}
		if(aa and b and c){
			x=max(x,a[p[i].ff][p[i].ss]+a[p[i].ff-1][p[i].ss]+a[p[i].ff][p[i].ss-1]+a[p[i].ff+1][p[i].ss]);
		}
		if(c and b and d){
			x=max(x,a[p[i].ff][p[i].ss]+a[p[i].ff][p[i].ss-1]+a[p[i].ff][p[i].ss+1]+a[p[i].ff+1][p[i].ss]);
		}
		sum+=x;
	}
	cout<<sum<<'\n';

}
 
int main(){
	// freopen("in.txt","w",stdout);
	// freopen("out.txt","r",stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll t=1;
	// cin>>t;
	while(t--) solve();
}

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