oj.uz

답안 #254126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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)