답안 #143696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143696 2019-08-14T22:50:30 Z tutis Coins (LMIO19_monetos) C++17
20 / 100
1811 ms 262144 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[102][102][100 * 100 / 2 + 10];
	for (int i = 0; i < 102; i++)
	{
		for (int j = 0; j < 102; j++)
		{
			for (int t = 0; t < 100 * 100 / 2 + 10; 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];
int ans[302][302];
void approx()
{
	const int sc = 3;
	k1 = 0;
	for (int i = 0; i < 300 / sc; i++)
	{
		for (int j = 0; j < 300 / sc; j++)
		{
			int k = 0;
			for (int x = 1; x <= sc; x++)
			{
				for (int y = 1; y <= sc; y++)
				{
					k += m[i * sc + x][j * sc + y];
				}
			}
			a[i + 1][300 / sc - j] = (k >= (sc * sc / 2));
		}
		for (int j = 0; j < 300 / sc; j++)
			a[i][j + 1] += a[i][j];
		k1 += a[i][300 / sc];
	}
	exact(300 / sc);
	k1 = n * n / 2;
	for (int i = 0; i < 300; i++)
	{
		for (int j = 0; j < 300; j++)
		{
			if (res[i / sc + 1][j / sc + 1])
			{
				ans[i][j] = 1;
				k1--;
			}
		}
	}
	for (int i = 0; i < 300; i++)
	{
		for (int j = 0; j < 300; j++)
		{
			if (k1 < 0 && ans[i][j] == 1)
			{
				k1++;
				ans[i][j] = 0;
			}
		}
	}
	for (int i = 299; i >= 0; i--)
	{
		for (int j = 299; j >= 0; j--)
		{
			if (k1 > 0 && ans[i][j] == 0)
			{
				k1--;
				ans[i][j] = 1;
			}
		}
	}
	for (int i = 0; i < 300; i++)
	{
		for (int j = 0; j < 300; 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 162 ms 204408 KB K = 17
2 Correct 197 ms 204536 KB K = 576
3 Runtime error 1806 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1772 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1711 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1811 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 1742 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 1754 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1809 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 1787 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)