2buttonsのeiya解

https://hoj.hamako-ths.ed.jp/onlinejudge/contest/121/problems/5
提出しても見られないみたいなのではるだけはっておきます。

ところで通常問題の方のURLをはりたかったのですが、なんかidがずれるみたいなのではりません。
現時点(2017/12/2)ではidは869です。

部分点(20点)

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;

int32_t H,W;
int32_t ah,aw,bh,bw;
int32_t map[1000][1000];
int32_t distA(int32_t h, int32_t w) { return std::abs(h - ah) + std::abs(w - aw); }
int32_t distB(int32_t h, int32_t w) { return std::abs(h - bh) + std::abs(w - bw); }

int64_t func(int32_t i, int32_t j, bool myturn)//Aがtrue、先行がtrue
{
	bool finish = true;
	for (int32_t h = 0; h < H; h++)
		for (int32_t w = 0; w < W; w++)
	{
		if (distA(h, w) >= i && distB(h, w) >= j) {
			finish = false;
		}
	}
	if (finish) {
		return 0;
	}

	auto pattA = func(i + 1, j, !myturn);
	if(myturn)
		for (int32_t h = 0; h < H; h++)
			for (int32_t w = 0; w < W; w++)
	{
		if (distA(h, w) == i && distB(h, w) >= j) {
			pattA += map[h][w];
		}
	}

	auto pattB = func(i, j + 1, !myturn);
	if (myturn)
		for (int32_t h = 0; h < H; h++)
			for (int32_t w = 0; w < W; w++)
	{
		if (distA(h, w) >= i && distB(h, w) == j) {
			pattB += map[h][w];
		}
	}

	if (myturn == (pattA>pattB)) {
		return pattA;
	}
	else {
		return pattB;
	}
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> H>>W;
	in >> ah >> aw >> bh >> bw; --ah; --aw; --bh; --bw;
	for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) {
		in >> map[h][w];
	}

	out << func(0, 0, true) << endl;;

	return 0;
}
#endif

満点

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


int32_t H, W;
int32_t ah, aw;
int32_t bh, bw;
int32_t map[1000][1000];

const int32_t DIST_MAX = 2000;
int64_t scoreA[DIST_MAX+2][DIST_MAX+2];//自分、相手
int64_t scoreB[DIST_MAX+2][DIST_MAX+2];//自分、相手

const int64_t INF = 100010002000000000;
int64_t dp[DIST_MAX + 2][DIST_MAX + 2];
int64_t func(int32_t a, int32_t b)
{
	if (a == DIST_MAX+1 && b == DIST_MAX+1)
	{
		return 0;
	}
	if (a > DIST_MAX+1 || b > DIST_MAX+1) {
		return INF;
	}
	if (dp[a][b] != INF) { return dp[a][b]; }
	return dp[a][b] = std::max(
		-func(a + 1, b) + scoreA[a][b],
		-func(a, b + 1) + scoreB[b][a]
	);
}

int main()
{
	using std::cin;
	using std::cout;
	using std::endl;
	for (auto& arr : dp)for (auto& i : arr) { i = INF; }
	cin >> H >> W;
	for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) {
		cin >> map[h][w];
	}
	cin >> ah >> aw >> bh >> bw; --ah; --aw; --bh; --bw;

	int64_t sum = 0;
	for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) {
		int32_t dist_a = std::abs(h - ah) + std::abs(w - aw);
		int32_t dist_b = std::abs(h - bh) + std::abs(w - bw);
		scoreA[dist_a][dist_b] += map[h][w];
		scoreB[dist_b][dist_a] += map[h][w];
		sum += map[h][w];
	}
	for (int32_t distme = 0; distme <= DIST_MAX; ++distme) {
		for (int32_t distopp = DIST_MAX-1; distopp >= 0; --distopp) {
			scoreA[distme][distopp] += scoreA[distme][distopp + 1];
			scoreB[distme][distopp] += scoreB[distme][distopp + 1];
		}
	}

	cout << (func(0, 0)+ sum)/2 << endl;
}