/*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)
{
const int sz = 77 * 77 / 2 + 5;
static int dp[77][77][sz + 1];
for (int i = 0; i < 77; i++)
{
for (int j = 0; j < 77; j++)
{
for (int t = 0; t <= sz; 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 t, n, k2;
int m[302][302];
int ans[302][302];
void 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;
}
}
}
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);
else
approx();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cout << res[i][j] << " ";
}
cout << "\n";
}
}
Compilation message
monetos.cpp: In function 'void approx()':
monetos.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < A.size() / 2; i++)
~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
69368 KB |
K = 17 |
| 2 |
Correct |
92 ms |
69624 KB |
K = 576 |
| 3 |
Partially correct |
309 ms |
70648 KB |
K = 18847 |
| 4 |
Partially correct |
313 ms |
70776 KB |
K = 21928 |
| 5 |
Partially correct |
327 ms |
70904 KB |
K = 17452 |
| 6 |
Partially correct |
310 ms |
70776 KB |
K = 20977 |
| 7 |
Partially correct |
308 ms |
70752 KB |
K = 21779 |
| 8 |
Incorrect |
311 ms |
70776 KB |
K = 20241 |
| 9 |
Incorrect |
310 ms |
70776 KB |
K = 21155 |
| 10 |
Partially correct |
318 ms |
70604 KB |
K = 20282 |
