提出 #3827541

---

ソースコード 拡げる

#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

const LL inf = 112345678901234567;
LL N;
std::vector<LL>x, c, v;
std::vector<std::vector<LL>>memo1, memo2;

LL dp1(LL b, LL i)
{
	if (memo1[b][i] != -1) return memo1[b][i];
	LL csum = 0, vsum = 0;
	rep(j, N)
	{
		if (b&(1LL << j))
		{
			csum += c[j];
			vsum += v[j];
		}
	}
	if (csum <= x[i]) return memo1[b][i] = vsum;
	LL res = 0;
	rep(j, N)
	{
		if (b&(1LL << j)) res = std::max(res, dp1(b ^ (1LL << j), i));
	}
	return memo1[b][i] = res;
}

LL dp2(LL b, LL i)
{
	if (i == N) return 0;
	if (i > N) return -inf;
	if (memo2[b][i] != -1) return memo2[b][i];
	LL res1 = inf;
	rep(j, N) if (b&(1LL << j)) res1 = std::min(res1, dp2(b ^ (1LL << j), i + 1));
	LL res2 = dp1(b, i);
	return memo2[b][i] = std::max(res1, res2);
}

int main()
{
	in >> N;
	x.resize(N + 1); c.resize(N); v.resize(N);
	rep(i, N) in >> x[i + 1];
	rep(i, N) in >> c[i];
	rep(i, N) in >> v[i];

	rep(i, N) x[i + 1] += x[i];
	memo1.resize((1LL << N));
	rep(i, memo1.size()) memo1[i].resize(N + 1, -1);
	memo2.resize((1LL << N));
	rep(i, memo2.size()) memo2[i].resize(N + 1, -1);
	out << dp2((1LL << N) - 1, 0) << std::endl;
}

提出情報

ジャッジ結果