oj.uz

Submission #254129

# Submission time Handle Problem Language Result Execution time Memory
254129 2020-07-29T11:48:02 Z rama_pang Coins (LMIO19_monetos) C++14
20 / 100
 400 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 76;
const int INF = 1e8;

int T, N, K1, K2;
int A[305][305];
int ans[305][305];

int L[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN * MAXN / 2];
pair<int, int> pr[MAXN][MAXN][MAXN * MAXN / 2];

void Solve() {
  int shift = max(1, N / 75);
  int NN = N / shift;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      int di = (i + shift - 1) / shift;
      int dj = (j + shift - 1) / shift;
      L[di][dj] += A[i][j];
    }
  }
  for (int i = 1; i <= NN; i++) {
    for (int j = 1; j <= NN; j++) {
      L[i][j] += L[i][j - 1];
    }
  }
  for (int i = 0; i < MAXN; i++) {
    for (int j = 0; j < MAXN; j++) {
      for (int k = 0; k < MAXN * MAXN / 2; k++) {
        dp[i][j][k] = INF;
        pr[i][j][k] = {-1, -1};
      }
    }
  }
  dp[NN + 1][0][0] = 0;
  for (int i = NN + 1; i >= 1; i--) {
    for (int j = 0; j <= NN; j++) {
      for (int k = 0; k <= NN * NN / 2; k++) if (dp[i][j][k] != INF) {
        if (k + j <= NN * NN / 2) {
          if (dp[i - 1][j][k + j] > dp[i][j][k] + L[i - 1][j]) {
            dp[i - 1][j][k + j] = dp[i][j][k] + L[i - 1][j];
            pr[i - 1][j][k + j] = {1, k};
          }
        }
        if (k <= NN * NN / 2) {
          if (dp[i][j + 1][k] > dp[i][j][k]) {
            dp[i][j + 1][k] = dp[i][j][k];
            pr[i][j + 1][k] = {0, k};
          }
        }
      }
    }
  }
  vector<vector<int>> res(NN + 2, vector<int>(NN + 2));
  int i = 1, j = NN, k = NN * NN / 2;
  while (i != NN + 1) {
    int ni, nj, nk;
    if (pr[i][j][k].first == 1) {
      for (int l = 1; l <= NN; l++) {
        res[i][l] = (l > j);
      }
      ni = i + 1, nj = j, nk = pr[i][j][k].second;
    } else {
      ni = i, nj = j - 1, nk = pr[i][j][k].second;
    }
    i = ni, j = nj, k = nk;
  }
  for (int i = 1; i <= NN; i++) {
    for (int j = 1; j <= NN; j++) {
      for (int k = 1; k <= shift; k++) {
        for (int l = 1; l <= shift; l++) {
          ans[(i - 1) * shift + k][(j - 1) * shift + l] = res[i][j];
        }
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> T >> N >> K1 >> K2;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      cin >> A[i][j];
    }
  }
  Solve();
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      cout << ans[i][j] << " \n"[j == N];
    }
  }
  return 0;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 196216 KB K = 17
2 Correct 111 ms 196344 KB K = 576
3 Runtime error 348 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 366 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 400 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 396 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 364 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 349 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 380 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 360 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)