답안 #143700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143700 2019-08-14T23:02:59 Z tutis Coins (LMIO19_monetos) C++17
20 / 100
302 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)
{
	int dp[n + 2][n + 2][n * n + 1];
	for (int i = 0; i < n + 2; i++)
	{
		for (int j = 0; j < n + 2; j++)
		{
			for (int t = 0; t <= n * n; 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 = 4;
	k1 = 0;
	vector<pair<int, pair<int, int>>>A;
	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.push_back({ -k, {i + 1, 300 / sc - j}});
			//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];
	}
	sort(A.begin(), A.end());
	for (int i = 0; i < A.size() / 2; i++)
	{
		a[A[i].second.first][A[i].second.second] = 1;
	}
	for (int i = 0; i < 300 / sc; i++)
	{
		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";
	}
}

Compilation message

monetos.cpp: In function 'void approx()':
monetos.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size() / 2; i++)
                  ~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB K = 17
2 Correct 57 ms 27004 KB K = 576
3 Runtime error 301 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 283 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 289 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 302 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 282 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 291 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 277 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 292 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)