POJ 2958

POJ ShortCoding

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

#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;
}

で、適当に縮める。

#import<algo.h>

int a, t, b, x, y, v[100], h[100], i, j;

int
o(int *d)
{
  int i, u, c;
  for (u=c=a=i=0;i<100;d[i++]=0)
    u+=d[i]*2,c+=u-t,a<?=c;
}

int
main()
{
  for(cin>>x;cin>>x>>y;cout<<b+o(h)+o(v)<<" blocks\n",t=b=0)
      for (i = 0; i < y; i++)
          for (j = 0; j < x; j++)
            cin>>a,h[i]+=a,v[j]+=a,b+=(i+j)*a,t+=a;
}

空白を削って 265B。まだまだ削れそうだけど、とりあえずこの辺で。