Submission #834314

#	Time	Username	Problem	Language	Result	Execution time	Memory
834314		tolbi	T-Covering (eJOI19_covering)	C++17	15 / 100	1095 ms	852 KiB

covering

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tol(bi) (1LL<<((int)(bi)))
int32_t main(){
	int h,w;
	cin>>h>>w;
	vector<vector<int>> val(h,vector<int>(w));
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; j++){
			cin>>val[i][j];
		}
	}
	int n;cin>>n;
	vector<vector<int>> arr(h,vector<int>(w,0));
	vector<pair<int,int>> spec(n);
	for (int i = 0; i < n; i++){
		int x,y;cin>>x>>y;
		arr[x][y]=i+1;
		spec[i]={x,y};
	}
	int ans = -1;
	for (int i = 0; i < tol(n*2); i++){
		int crans = 0;
		bool boolean=true;
		vector<pair<int,int>> tb;
		for (int j = 0; j < n; j++){
			int a = !(tol(j*2)&i);
			int b = !(tol(j*2+1)&i);
			int x = spec[j].first;
			int y = spec[j].second;
			crans+=val[x][y];

			if (a!=0 || b!=0){
				if (x==0 || arr[x-1][y]!=0){
					boolean=false;
					break;
				}
				arr[x-1][y]=-1;
				crans+=val[x-1][y];
				tb.push_back({x-1,y});
			}
			if (a!=0 || b!=1){
				if (y==0 || arr[x][y-1]!=0){
					boolean=false;
					break;
				}
				arr[x][y-1]=-1;
				crans+=val[x][y-1];
				tb.push_back({x,y-1});
			}
			if (a!=1 || b!=0){
				if (x==h-1 || arr[x+1][y]!=0){
					boolean=false;
					break;
				}
				arr[x+1][y]=-1;
				crans+=val[x+1][y];
				tb.push_back({x+1,y});
			}
			if (a!=1 || b!=1){
				if (y==w-1 || arr[x][y+1]!=0){
					boolean=false;
					break;
				}
				arr[x][y+1]=-1;
				crans+=val[x][y+1];
				tb.push_back({x,y+1});
			}
		}
		while (tb.size()){
			arr[tb.back().first][tb.back().second]=0;
			tb.pop_back();
		}
		if (!boolean) continue;
		ans=max(ans,crans);
	}
	if (ans==-1) cout<<"No"<<endl;
	else cout<<ans<<endl;
}

• Subtask 1: 0 / 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