oj.uz

Submission #254126

# Submission time Handle Problem Language Result Execution time Memory
254126 2020-07-29T11:45:57 Z rama_pang Coins (LMIO19_monetos) C++14
0 / 100
 401 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 != -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 353 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 393 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 363 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 387 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 369 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 371 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 381 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 362 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 386 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 401 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)