oj.uz

Submission #143711

# Submission time Handle Problem Language Result Execution time Memory
143711 2019-08-14T23:15:50 Z tutis Coins (LMIO19_monetos) C++17
20 / 100
 422 ms 205568 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 res[302][302];
int k1;
void exact(int n, bool pri = false)
{
	const int sz = 100;
	static int dp[sz + 2][sz + 2][sz * sz / 2 + 2];
	for (int i = 0; i < sz + 2; i++)
	{
		for (int j = 0; j < sz + 2; j++)
		{
			for (int t = 0; t < sz * sz / 2 + 2; 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++;
	}
	if (pri)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				cout << res[i][j] << " ";
			}
			cout << "\n";
		}
		exit(0);
	}
}
int t, n, k2;
int m[302][302];
int ans[300][300];
pair<int, int*> approx()
{
	const int sc = 4;
	k1 = 0;
	vector<pair<int, pair<int, int>>>A;
	for (int i = 0; i < 300 / sc; i++)
	{
		for (int j = 0; j < 300 / sc; j++)
		{
			int k = 0;
			for (int x = 1; x <= sc; x++)
			{
				for (int y = 1; y <= sc; y++)
				{
					k += m[i * sc + x][j * sc + y];
				}
			}
			A.push_back({ -k, {i + 1, 300 / sc - j}});
			a[i + 1][300 / sc - j] = 0;
		}
		for (int j = 0; j < 300 / sc; j++)
			a[i][j + 1] += a[i][j];
		k1 += a[i][300 / sc];
	}
	sort(A.begin(), A.end());
	for (int i = 0; i < A.size() / 2; i++)
	{
		a[A[i].second.first][A[i].second.second] = 1;
	}
	for (int i = 0; i < 300 / sc; i++)
	{
		for (int j = 0; j < 300 / sc; j++)
			a[i][j + 1] += a[i][j];
		k1 += a[i][300 / sc];
	}
	exact(300 / sc);
	k1 = n * n / 2;
	for (int i = 0; i < 300; i++)
	{
		for (int j = 0; j < 300; j++)
		{
			if (res[i / sc + 1][j / sc + 1])
			{
				ans[i][j] = 1;
				k1--;
			}
		}
	}
	for (int i = 0; i < 300; i++)
	{
		for (int j = 0; j < 300; j++)
		{
			if (k1 < 0 && ans[i][j] == 1)
			{
				k1++;
				ans[i][j] = 0;
			}
		}
	}
	for (int i = 299; i >= 0; i--)
	{
		for (int j = 299; j >= 0; j--)
		{
			if (k1 > 0 && ans[i][j] == 0)
			{
				k1--;
				ans[i][j] = 1;
			}
		}
	}
	return make_pair(0, ans[0]);

	for (int i = 0; i < 300; i++)
	{
		for (int j = 0; j < 300; j++)
		{
			cout << ans[i][j] << " ";
		}
		cout << "\n";
	}
	exit(0);
}
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, true);
	auto r = approx();
	auto c = r.second;
	for (int i = 0; i < 300; i++)
	{
		for (int j = 0; j < 300; j++)
		{
			cout << *(c + i * 300 + j);
		}
		cout << "\n";
	}
}

Compilation message

monetos.cpp: In function 'std::pair<int, int*> approx()':
monetos.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size() / 2; i++)
                  ~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 204024 KB K = 17
2 Correct 197 ms 204152 KB K = 576
3 Incorrect 416 ms 205236 KB Expected integer, but "000000000000000000000000000000...0000000000000000000000000000000" found
4 Incorrect 422 ms 205568 KB Expected integer, but "000000000000000000000000000000...0000000000000000000000000000000" found
5 Incorrect 413 ms 205392 KB Expected integer, but "000000000000000000000000000000...1111111111111111111111111111111" found
6 Incorrect 418 ms 205468 KB Expected integer, but "000000000000000000000000000000...0000000000000000000000011111111" found
7 Incorrect 422 ms 205392 KB Expected integer, but "000000000000000000000000000000...0000000000000000000000000000000" found
8 Incorrect 419 ms 205520 KB Expected integer, but "000000000000000000000000000000...1111111111111111111111111111111" found
9 Incorrect 414 ms 205392 KB Expected integer, but "000000000000000000000000000000...1111111111111111111111111111111" found
10 Incorrect 417 ms 205340 KB Expected integer, but "000000000000000000000000000000...0000000000000000000000000000000" found