Submission #577196

#	Time	Username	Problem	Language	Result	Execution time	Memory
577196		dozer	T-Covering (eJOI19_covering)	C++14	25 / 100	70 ms	19948 KiB

covering

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005
#define L(node) node * 2
#define R(node) node * 2 + 1
#define int long long

const int modulo = 1e9 + 7; 

int32_t main()
{
	fastio();

	pii dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	pii dia[4] = {{1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
	int n, m;
	cin>>n>>m;
	int arr[n + 5][m + 5], done[n + 5][m + 5];
	memset(done , -1, sizeof(done));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cin>>arr[i][j], done[i][j] = 0;
	}
	int k;
	cin>>k;
	set<pii> spe;
	int ans = 0;
	for (int i = 1; i <= k; i++)
	{
		int x, y;
		cin>>x>>y;
		spe.insert({x + 1, y + 1});
		done[x + 1][y + 1] = 2;
		ans += arr[x + 1][y + 1];
	}
	//handle the ones that have only one way of placement
	vector<pii> tmp(spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		int cnt = 0, mini = modulo;
		for (int j = 0; j < 4; j++)
		{
			int a = dir[j].st, b = dir[j].nd;
			if (done[x + a][y + b] == 0) cnt++, mini = min(mini, arr[x + a][y + b]);
		}
		if (cnt < 3)
		{
			cout<<"No\n";
			return 0;
		}
		if (cnt == 3)
		{
			for (int j = 0; j < 4; j++)
			{
				int a = dir[j].st, b = dir[j].nd;
				if (done[x + a][y + b] == 0) done[x + a][y + b] = 1, ans += arr[x + a][y + b];
			}
			done[x][y] = 1;
			spe.erase(i);
			continue;
		}
	}
	//handle the diagonals, which have only one way of placement
	tmp = vector<pii> (spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		if (done[x][y] == 1) continue;
		int cnt = 0, mini = modulo;
		pii ne;
		for (int j = 0; j < 4; j++)
		{
			int a = dia[j].st, b = dia[j].nd;
			if (done[x + a][y + b] == 2) cnt++, ne = {a, b};
		}
		if (cnt > 1)
		{
			cout<<"No\n";
			return 0;
		}
		if (cnt == 1)
		{
			int c = ne.st, d = ne.nd;
			done[x][y] = 1;
			done[x + c][y + d] = 1;
			spe.erase({x, y});
			spe.erase({x + c, y + d});
			cnt = 0;
			for (int j = 0; j < 4; j++)
			{
				int a = dir[j].st, b = dir[j].nd;
				if (done[x + a][y + b] == 0) cnt++, ans += arr[x + a][y + b], done[x + a][y + b] = 1;
			}
			if (done[x + 2 * c][y + d] == 0) cnt++, ans += arr[x + 2 * c][y + d], done[x + 2 * c][y + d] = 1;
			if (done[x + c][y + 2 * d] == 0) cnt++, ans += arr[x + c][y + 2 * d], done[x + c][y + 2 * d] = 1;
			if (cnt < 6) 
			{
				cout<<"No\n";
				return 0;
			}
		}
	}
	//handle the one that are left with one way of placement after placing the diagonals
	tmp = vector<pii> (spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		int cnt = 0, mini = modulo;
		for (int j = 0; j < 4; j++)
		{
			int a = dir[j].st, b = dir[j].nd;
			if (done[x + a][y + b] == 0) cnt++, mini = min(mini, arr[x + a][y + b]);
		}
		if (cnt < 3)
		{
			cout<<"No\n";
			return 0;
		}
		if (cnt == 3)
		{
			for (int j = 0; j < 4; j++)
			{
				int a = dir[j].st, b = dir[j].nd;
				if (done[x + a][y + b] == 0) done[x + a][y + b] = 1, ans += arr[x + a][y + b];
			}
			done[x][y] = 1;
			spe.erase(i);
			continue;
		}
	}
	//todo: handle the components which have one square between each other
	/*
	tmp = vector<pii> (spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		for (int j = 0; j < 4; j++)
		{
			int a = dir[j].st, b = dir[j].nd;
			if 
		}
	}
	*/

	//todo: choose the minimum ones
	tmp = vector<pii> (spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		int cnt = 0, mini = modulo;
		pii ne;
		for (int j = 0; j < 4; j++)
		{
			int a = dir[j].st, b = dir[j].nd;
			if (done[x + a][y + b] == 0)
			{
				if (mini > arr[x + a][y + b]) ne = {x + a, y + b};
				cnt++, mini = min(mini, arr[x + a][y + b]), ans += arr[x + a][y + b], done[x + a][y + b] = 1;
			}
		}
		if (cnt < 3)
		{
			cout<<"No\n";
			return 0;
		}
		done[x][y] = 1;
		spe.erase(i);
		if (cnt == 4)
		{
			//cout<<ne.st<<sp<<ne.nd<<endl;
			done[ne.st][ne.nd] = 0;
			ans -= arr[ne.st][ne.nd];
		}
	}
	cout<<ans<<endl;
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Compilation message (stderr)

covering.cpp: In function 'int32_t main()':
covering.cpp:79:16: warning: unused variable 'mini' [-Wunused-variable]
   79 |   int cnt = 0, mini = modulo;
      |                ^~~~

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