oj.uz

Submission #263153

# Submission time Handle Problem Language Result Execution time Memory
263153 2020-08-13T13:35:22 Z Berted Coins (LMIO19_monetos) C++14
95.0478 / 100
 63 ms 33052 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[301][301], ans[301][301];

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 = 6;}
	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
95.0478009703 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB K = 17
2 Correct 28 ms 32504 KB K = 576
3 Partially correct 61 ms 33016 KB K = 18700
4 Partially correct 60 ms 32888 KB K = 21869
5 Partially correct 61 ms 33016 KB K = 17242
6 Partially correct 60 ms 33052 KB K = 20929
7 Partially correct 63 ms 32888 KB K = 21508
8 Partially correct 60 ms 33016 KB K = 19704
9 Partially correct 60 ms 33016 KB K = 20822
10 Partially correct 60 ms 32880 KB K = 20240