oj.uz

Submission #254128

# Submission time Handle Problem Language Result Execution time Memory
254128 2020-07-29T11:46:49 Z rama_pang Coins (LMIO19_monetos) C++14
0 / 100
 195 ms 213764 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 65;
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 / 60);
  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 != -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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 168 ms 212728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 177 ms 212856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 186 ms 213764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 195 ms 213476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 185 ms 213496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 184 ms 213496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 185 ms 213624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 183 ms 213496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 195 ms 213496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 188 ms 213500 KB Execution killed with signal 11 (could be triggered by violating memory limits)