배열 B의 값

Problem link: https://www.acmicpc.net/problem/16971

그림을 그려보면 어렵지 않게 풀 수 있다.

임의의 체스판이 주어졌을 때 각 원소가 몇 번씩 더해지는지를 그림으로 표현해보면 아래와 같다.

• 황색 영역 : 1번 더해짐
• 청색 영역 : 2번 더해짐
• 적색 영역 : 3번 더해짐

아무런 변경을 하지 않은 상태에서 B의 합을 B_init이라고 하자.

이제 행을 바꾸는 연산을 통해 더 큰 B를 만들 수 있는지를 알아볼텐데, 그림을 잘 살펴보면 [1, N-1] 구간에 있는 행들끼리 바꾸는 것은 아무의미가 없는 것을 알 수 있다.

왜냐하면 어차피 바꿀 두 행에 적용될 가중치(몇 번씩 더해지느냐)가 같기 때문이다.

따라서, 첫 행 또는 마지막 행과 [1, N-1] 구간 중 하나의 행을 골라 교환하는 것이 답이 될 가능성이 있다.

이때, 실제로 두 행을 교환하고 합을 구해보는 연산을 반복한다면, 시간 초과를 맞게 될 것이다.

실제로 두 행을 교환하고 합을 구하는 연산 대신 아래의 아이디어를 활용해보자.

• 각 행에 대해서 R[r] 값을 관리하자.
• R[r]의 값은 1 * R[r][0] + 2 * R[r][1] + 2 * R[r][2] + ... + 2 * R[r][W-2] + 1 * R[r][W-1]과 같이 정의한다.
  (즉, 첫번째와 마지막의 원소에만 가중치를 1을 주고 나머지 원소에는 가중치 2를 준다)
• 0번 행과 x번 행(1 <= x <= W-2)을 교환한다면 이 때 B의 합은 B_init + R[0] - R[x]가 된다.
• 이는 다시 그림을 잘 살펴보면 이해할 수 있는데, 0번 행은 가중치 1 2 2 ... 2 1이 적용된 행이며, x번 행은 가중치 2 4 4 ... 4 2가 적용된 행이다.
• 두 행을 교환한다는 이야기는 곧 x번 행의 가중치와 0번 행의 가중치를 교환한다는 이야기이고, 이는 합 관점에서 B_init + R[0] - R[x]와 같은 이야기이다.

#include <iostream>
#include <algorithm>
#include <cstdint>

using namespace std;

const int kMaxH = 1000;
const int kMaxW = 1000;

int H;
int W;
int A[kMaxH][kMaxW];
int R[kMaxH];
int C[kMaxW];

int64_t GetSum()
{
  int64_t ret = 0;

  for (int r = 0; r < H - 1; ++r)
  {
    for (int c = 0; c < W - 1; ++c)
    {
      ret += A[r][c] + A[r + 1][c] + A[r][c + 1] + A[r + 1][c + 1];
    }
  }

  return ret;
}

int64_t Solve()
{
  for (int r = 0; r < H; ++r)
  {
    R[r] = 0;
    for (int c = 0; c < W; ++c)
    {
      R[r] += 2 * A[r][c];
    }

    R[r] -= A[r][0] + A[r][W - 1];
  }

  for (int c = 0; c < W; ++c)
  {
    C[c] = 0;
    for (int r = 0; r < H; ++r)
    {
      C[c] += 2 * A[r][c];
    }

    C[c] -= A[0][c] + A[H - 1][c];
  }

  int64_t ans_no = GetSum();

  int64_t ans_row = ans_no;
  for (int r = 1; r < H - 1; ++r)
  {
    ans_row = max(ans_row, ans_no - R[r] + R[0]);
    ans_row = max(ans_row, ans_no - R[r] + R[H - 1]);
  }

  int64_t ans_col = ans_no;
  for (int c = 1; c < W - 1; ++c)
  {
    ans_col = max(ans_col, ans_no - C[c] + C[0]);
    ans_col = max(ans_col, ans_no - C[c] + C[W - 1]);
  }

  return max(ans_no, max(ans_col, ans_row));
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read inputs
  cin >> H >> W;
  for (int r = 0; r < H; ++r)
  {
    for (int c = 0; c < W; ++c)
    {
      cin >> A[r][c];
    }
  }

  // Solve
  cout << Solve() << '\n';

  return 0;
}