oj.uz

Submission #143686

# Submission time Handle Problem Language Result Execution time Memory
143686 2019-08-14T22:18:54 Z tutis Coins (LMIO19_monetos) C++17
20 / 100
 83 ms 59256 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 t, n, k1, k2;
int res[302][302];
int dp[52][52][52 * 52];
void exact()
{
	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 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 >> a[i][n - j];
		for (int j = 0; j < n; j++)
			a[i][j + 1] += a[i][j];
		k1 += a[i][n];
	}
	exact();
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << res[i][j] << " ";
		}
		cout << "\n";
	}
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28920 KB K = 17
2 Correct 59 ms 29064 KB K = 576
3 Runtime error 83 ms 59128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 73 ms 59104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 73 ms 59128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 72 ms 59100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 73 ms 59256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 72 ms 59128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 73 ms 59172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 82 ms 59128 KB Execution killed with signal 11 (could be triggered by violating memory limits)