oj.uz

Submission #367927

# Submission time Handle Problem Language Result Execution time Memory
367927 2021-02-18T21:15:58 Z Kenzo_1114 Cultivation (JOI17_cultivation) C++17
0 / 100
 97 ms 492 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 310;

int n, m, p, ans = 12;
bool mark[MAXN][MAXN];

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

bool valid()
{
	bool ok = true;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			ok &= mark[i][j];
	return ok;
}

void BKT(int moves)
{
	if(moves >= ans)	return;
	if(valid())	{	ans = min(ans, moves); return;	}

	bool cur[5][5];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cur[i][j] = mark[i][j];

	for(int k = 0; k < 4; k++)
	{
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
			{
				int ni = i + dx[k];
				int nj = j + dy[k];

				mark[i][j] = cur[i][j] || cur[ni][nj];
			}

		BKT(moves + 1);
	}

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			mark[i][j] = cur[i][j];
}

int main ()
{
	scanf("%d %d %d", &n, &m, &p);

	for(int i = 0, x, y; i < p; i++)
	{
		scanf("%d %d", &x, &y);
		mark[x][y] = true;
	}

	if(n <= 4 && m <= 4)
	{
		BKT(0);
		printf("%d\n", ans);
	}
	else	printf("0\n");
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |  scanf("%d %d %d", &n, &m, &p);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 97 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 97 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 97 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 97 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -