답안 #143687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143687 2019-08-14T22:39:41 Z tutis Coins (LMIO19_monetos) C++17
20 / 100
75 ms 60024 KB
/*input
0 4 1 5
0 0 1 0
0 0 0 1
0 1 1 1
1 1 0 1
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int a[302][302];
int res[302][302];
int k1;
void exact(int n)
{
	static int dp[52][52][52 * 52];
	for (int i = 0; i < 52; i++)
	{
		for (int j = 0; j < 52; j++)
		{
			for (int t = 0; t < 52 * 52; t++)
				dp[i][j][t] = -1000000;
		}
	}
	dp[n + 1][n][0] = 0;
	for (int i = n; i >= 1; i--)
	{
		for (int j = 0; j <= n; j++)
		{
			for (int j1 = j; j1 <= n; j1++)
			{
				for (int k = 0; k + j <= k1; k++)
				{
					dp[i][j][k + j] = max(dp[i][j][k + j], dp[i + 1][j1][k] + a[i][j]);
				}
			}
		}
	}
	int i = 1;
	pair<int, int>mx = { -2, -2};
	for (int j = 0; j <= n; j++)
		mx = max(mx, {dp[i][j][k1], j});
	int j = mx.second;
	int k = k1;
	while (i <= n)
	{
		for (int t = 0; t < j; t++)
		{
			res[i][n - t] = 1;
		}
		int j1 = -1;
		for (int jj = j; jj <= n; jj++)
		{
			if (dp[i][j][k] == dp[i + 1][jj][k - j] + a[i][j])
				j1 = jj;
		}
		assert(j1 != -1);
		k -= j;
		j = j1;
		i++;
	}
}
int t, n, k2;
int m[302][302];
void approx()
{
	k1 = 0;
	for (int i = 0; i < 50; i++)
	{
		for (int j = 0; j < 50; j++)
		{
			int k = 0;
			for (int x = 1; x <= 6; x++)
			{
				for (int y = 1; y <= 6; y++)
				{
					k += m[i * 6 + x][j * 6 + y];
				}
			}
			a[i + 1][n - j] = (k >= 18);
		}
		for (int j = 0; j < n; j++)
			a[i][j + 1] += a[i][j];
		k1 += a[i][n];
	}
	exact(50);
	k1 = n * n / 2;
	int ans[300][300];
	for (int i = 0; i < 300; i++)
	{
		for (int j = 0; j < 300; j++)
		{
			if (res[i / 6 + 1][j / 6 + 1])
			{
				ans[i][j] = 1;
				k1--;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (k1 < 0 && ans[i][j] == 1)
			{
				k1++;
				ans[i][j] = 0;
			}
		}
	}
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = n - 1; j >= 0; j--)
		{
			if (k1 > 0 && ans[i][j] == 0)
			{
				k1--;
				ans[i][j] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << ans[i][j] << " ";
		}
		cout << "\n";
	}
	exit(0);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin >> t >> n >> k1 >> k2;
	k1 = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> m[i][j];
			a[i][n - j] = m[i][j];
		}
		for (int j = 0; j < n; j++)
			a[i][j + 1] += a[i][j];
		k1 += a[i][n];
	}
	if (n <= 50)
		exact(n);
	else
		approx();
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << res[i][j] << " ";
		}
		cout << "\n";
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 29048 KB K = 17
2 Correct 57 ms 29176 KB K = 576
3 Runtime error 74 ms 60024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 74 ms 59868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 74 ms 60024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 75 ms 59868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 74 ms 59896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 74 ms 59896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 73 ms 59896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 74 ms 59896 KB Execution killed with signal 11 (could be triggered by violating memory limits)