oj.uz

Submission #263146

# Submission time Handle Problem Language Result Execution time Memory
263146 2020-08-13T13:34:08 Z Berted Coins (LMIO19_monetos) C++14
20 / 100
 156 ms 97016 KB 
#include <iostream>
#include <assert.h>
using namespace std;
const int INF = 1e9;

int S;

int t, n, k1, k2, c, dp[63][63][2001], par[63][63][2001];
int ar[63][63], ans[63][63];

inline int getSum(int i1, int j1, int i2, int j2)
{
	return ar[i2][j2] - ar[i1 - 1][j2] - ar[i2][j1 - 1] + ar[i1 - 1][j1 - 1];
}

int main()
{
	cin >> t >> n >> k1 >> k2;
	if (n <= 50) {S = 1;}
	else {S = 5;}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int val; cin >> val;
			ar[i / S + 1][j / S + 1] += val;
		}
	}

	int ns = n / S;

	for (int i = 1; i <= ns + 1; i++)
	{
		for (int j = 1; j <= ns + 1; j++)
		{
			ar[i][j] += ar[i - 1][j];
			ar[i][j] += ar[i][j - 1];
			ar[i][j] -= ar[i - 1][j - 1];
		}
	}
	
	for (int i = 1; i <= ns; i++)
	{
		for (int j = 1; j <= ns + 1; j++)
		{
			for (int k = 0; 2 * k <= ns * ns; k++)
			{
				dp[i][j][k] = -INF;
			}
		}
	}

	dp[1][ns + 1][0] = 0;

	for (int i = 1; i <= ns; i++)
	{
		for (int j = ns + 1; j > 0; j--)
		{
			for (int k = 0; 2 * k <= ns * ns; k++)
			{
				if (dp[i][j][k] == -INF)
				{
					if (j <= ns && k >= ns - i + 1)
					{
						if (dp[i][j + 1][k - (ns - i + 1)] > -INF && dp[i][j + 1][k - (ns - i + 1)] + getSum(i, j, ns + 1, j) > dp[i][j][k])
						{
							dp[i][j][k] = dp[i][j + 1][k - (ns - i + 1)] + getSum(i, j, ns + 1, j);
							par[i][j][k] = 0;
						}
					}
					if (i > 1)
					{
						if (dp[i - 1][j][k] > -INF && dp[i - 1][j][k] > dp[i][j][k])
						{
							dp[i][j][k] = dp[i - 1][j][k];
							par[i][j][k] = 1;
						}
					}
					//cout << i << " " << j << " " << k << " " << dp[i][j][k] << "\n";
				}
			}
		}
	}

	int pi = ns, pj = 1, pk = ns * ns / 2, cnt = 0;

	//cout << "Best : " << dp[pi][pj][pk] << "\n";

	while (pj <= ns)
	{
		//cout << pi << " " << pj << " " << pk << " " << dp[pi][pj][pk] << " " << par[pi][pj][pk] << "\n";
		if (par[pi][pj][pk]) {pi--;}
		else
		{
			for (int i = (pi - 1) * S; i < n; i++)
			{
				for (int j = (pj - 1) * S; j < pj * S; j++)
				{
					ans[i][j] = 1;
					cnt += ans[i][j];
				}
			}
			pj++; pk -= (ns - pi + 1);
		}
	}

	assert(cnt == n * n / 2);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			assert(0 <= ans[i][j] && ans[i][j] <= 1);
			cout << ans[i][j];
			if (j + 1 < n) cout << " ";
		}
		cout << "\n";
	}
	return 0;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB K = 17
2 Correct 29 ms 32512 KB K = 576
3 Runtime error 150 ms 96844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 151 ms 97016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 79 ms 48120 KB K = 22475
6 Incorrect 88 ms 48120 KB improper placement
7 Incorrect 81 ms 48120 KB improper placement
8 Incorrect 81 ms 48120 KB K = 22560
9 Incorrect 79 ms 48120 KB K = 22594
10 Runtime error 156 ms 96888 KB Execution killed with signal 11 (could be triggered by violating memory limits)