oj.uz

Submission #834314

# Submission time Handle Problem Language Result Execution time Memory
834314 2023-08-22T12:58:34 Z tolbi T-Covering (eJOI19_covering) C++17
15 / 100
 1000 ms 852 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 444 KB Output is correct
2 Execution timed out 1085 ms 824 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 440 KB Output is correct
2 Execution timed out 1058 ms 852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 440 KB Output is correct
2 Execution timed out 1095 ms 724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 292 KB Output is correct
2 Execution timed out 1053 ms 212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 284 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 142 ms 284 KB Output is correct
4 Correct 29 ms 284 KB Output is correct
5 Correct 121 ms 284 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 444 KB Output is correct
2 Execution timed out 1085 ms 824 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 444 KB Output is correct
2 Execution timed out 1085 ms 824 KB Time limit exceeded
3 Halted 0 ms 0 KB -