POJ 2958

• ref:POJ 2958 -- Pizza delivery

解き方に気づけば簡単。ちなみに最初に斜めのラインで部分和を計算しておけば、とか思ったけどナイーブな方法と変わらないぐらい遅かった。

#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

static const int N = 100;

static int
optimal(int *d, int n, int total)
{
  int upside = 0;
  int downside = total;
  int m = 0;
  int cur = 0;

  for (int i = 0; i < n - 1; i++)
    {
      upside += d[i];
      downside -= d[i];
      cur += upside - (total - upside);
      m = cur < m ? cur : m;
    }

  return m;
}

int
main()
{
  int t;
  cin >> t;
  while (t--)
    {
      int rows, columns;
      int base_cost = 0;        // cost from (0, 0)
      int total = 0;            // sum of count for all blocks
      int sum_v[N];             // sum of count for each vertical area
      int sum_h[N];             // sum of count for each horizontal area

      cin >> columns >> rows;
      fill(sum_h, sum_h + rows, 0);
      fill(sum_v, sum_v + columns, 0);

      for (int i = 0; i < rows; i++)
        {
          for (int j = 0; j < columns; j++)
            {
              int x;
              cin >> x;
              sum_h[i] += x;
              sum_v[j] += x;
              base_cost += (i + j) * x;
            }

          total += sum_h[i];
        }

      int result = base_cost
        + optimal(sum_h, rows, total)
        + optimal(sum_v, columns, total);
      cout << result << " blocks" << endl;
    }

  return 0;
}

で、適当に縮める。