Submission #143697

#	Time	Username	Problem	Language	Result	Execution time	Memory
143697		tutis	Coins (LMIO19_monetos)	C++17	20 / 100	243 ms	262148 KiB

monetos

/*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()
{

	static int dp[302][300 / 10 + 2][(300 * 300) / 10 + 2];
	for (int i = 0; i < 302; i++)
	{
		for (int j = 0; j < 300 / 10 + 2; j++)
		{
			for (int t = 0; t < (300 * 300) / 10 + 2; t++)
				dp[i][j][t] = -1000000;
		}
	}
	dp[n + 1][300 / 10][0] = 0;
	for (int i = n; i >= 1; i--)
	{
		for (int j = 0; j <= n; j += 10)
		{
			for (int j1 = j; j1 <= n; j1 += 10)
			{
				for (int k = 0; k + j <= k1; k += 10)
				{
					dp[i][j / 10][(k + j) / 10] = max(
					                                  dp[i][j / 10][(k + j) / 10],
					                                  dp[i + 1][(j1) / 10][(k) / 10] + a[i][j]);
				}
			}
		}
	}
	int i = 1;
	pair<int, int>mx = { -2, -2};
	for (int j = 0; j <= n; j += 10)
		mx = max(mx, {dp[i][j / 10][k1 / 10], 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 += 10)
		{
			if (dp[i][j / 10][k / 10] == dp[i + 1][jj / 10][(k - j) / 10] + a[i][j])
				j1 = jj;
		}
		assert(j1 != -1);
		k -= j;
		j = j1;
		i++;
	}
}
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";
	}
}

• Subtask 1: 20 / 100