oj.uz

Submission #263200

# Submission time Handle Problem Language Result Execution time Memory
263200 2020-08-13T14:01:27 Z Berted Coins (LMIO19_monetos) C++14
98.906 / 100
 311 ms 204536 KB 
#include <iostream>
#include <assert.h>
#include <bitset>
using namespace std;
const int INF = 1e9;

int S;

int t, n, k1, k2, c, dp[103][103][5001];
bitset<5001> par[103][103];
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 = 3;}
	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 = (ns + 1 - i) * (ns + 1 - j); 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(1, j, i - 1, j) < dp[i][j][k])
						{
							dp[i][j][k] = dp[i][j + 1][k - (ns - i + 1)] + getSum(1, j, i - 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
98.9059950817 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB K = 17
2 Correct 24 ms 24832 KB K = 576
3 Correct 278 ms 204420 KB K = 18652
4 Correct 280 ms 204536 KB K = 21832
5 Correct 272 ms 204536 KB K = 17151
6 Partially correct 286 ms 204504 KB K = 20876
7 Correct 311 ms 204536 KB K = 21477
8 Partially correct 297 ms 204536 KB K = 19640
9 Partially correct 311 ms 204536 KB K = 20792
10 Partially correct 287 ms 204536 KB K = 20180