提出 #33832428

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 16;
const int MAXpower2_n = 65536;

template <typename T>
inline void read(T &a) {
	char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
	read(a), read(argv...);
}

int n, power2n;
int a[MAXpower2_n + 10][MAXn + 10];

#define ls (id << 1)
#define rs (id << 1 | 1)
const int MAXnd = MAXpower2_n * 4;
int le[MAXnd + 10], ri[MAXnd + 10], len[MAXnd + 10], mid[MAXnd + 10];
vector<int> d[MAXnd + 10]; int mxd[MAXnd + 10];
void build(int id, int l, int r, int lay) {
	le[id] = l;
	ri[id] = r;
	mid[id] = (l + r) >> 1;
	len[id] = r - l + 1;
	d[id].resize(len[id]);
	if (le[id] == ri[id]) {
		d[id][0] = 0;
		mxd[id] = 0;
	} else {
		build(ls, le[id], mid[id], lay - 1);
		build(rs, mid[id] + 1, ri[id], lay - 1);
		for (int i = 0, I = 0; i < len[ls]; ++i, ++I) {
			d[id][I] = d[ls][i] + mxd[rs] + (a[le[id] + I][lay] - a[le[id] + I][lay - 1]);
			mxd[id] = max(mxd[id], d[id][I]);
		}
		for (int i = 0, I = mid[id] - le[id] + 1; i < len[rs]; ++i, ++I) {
			d[id][I] = d[rs][i] + mxd[ls] + (a[le[id] + I][lay] - a[le[id] + I][lay - 1]);
			mxd[id] = max(mxd[id], d[id][I]);
		}
	}
}

signed main() {
	read(n);
	power2n = 1;
	for (int i = 1; i <= n; ++i) power2n *= 2;
	for (int i = 1; i <= power2n; ++i) {
		for (int j = 1; j <= n; ++j) {
			read(a[i][j]);
		}
	}
	build(1, 1, power2n, n);
	printf("%lld\n", mxd[1]);
}

提出情報

ジャッジ結果