Submission #2106440


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
typedef long long int ll;
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
const ll INF = 1e17;

//s[i]=i番目まで売ったときの合計金額
ll N, ans = 0;
ll c[20], x[20], v[20], s[21];
ll dp[(1 << 18) + 10];
ll gdp[19][(1 << 18) + 10];
//x=最大容量をnで表す y=残ってる商品のbit z=今の重さ(価値)
ll GDP(ll x, ll y, ll z) {
	ll res = 0;
	if (y == 0)return 0;
	if (gdp[x][y] != -1)return gdp[x][y];
	//最大容量より合計が少ない場合は価値を算出
	if (z <= s[x]) {
		REP(i, N) {
			if (y&(1 << i))res += v[i];
		}
	}
	ll buff = 0;
	//どの組み合わせが価値が最大になるかを全探索
	//ここでは入れない商品を全通り試して最大になるものを探しています
	REP(i, N) {
		if (y&(1 << i)) {
			buff = max(buff, GDP(x, y ^ (1 << i), z - c[i]));
		}
	}
	return gdp[x][y] = max(res, buff);
}
//x=何個目まで売ったか y=残ってる商品のbit
ll DP(ll x, ll y) {
	if (dp[y] != -1)return dp[y];
	if (y == 0)return dp[y] = 0;
	ll res = INF, wei = 0;
	REP(i, N) {
		//どの商品を減らすと相手の得る価値を最小化できるか全探索
		if (y&(1 << i)) {
			res = min(res, DP(x + 1, y ^ (1 << i)));
			wei += c[i];
		}
	}
	//GDPはyの状態で買う選択した時の最大値
	//resはまだ売り続けたときの最大値が返えってきます
	return dp[y] = max(GDP(x, y, wei), res);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin >> N;
	REP(i, N) { cin >> x[i]; s[i + 1] = x[i]; }
	REP(i, N)cin >> c[i];
	REP(i, N)cin >> v[i];
	REP(i, N + 1)s[i + 1] += s[i];
	REP(i, (1 << 18) + 10)dp[i] = -1;
	REP(i, 19)REP(j, (1 << 18) + 10)gdp[i][j] = -1;
	ans = DP(0, (1 << N) - 1);
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task C - 駆引取引
User Nafmo2
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1833 Byte
Status
Exec Time 347 ms
Memory 41216 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt
All 500 / 500 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt
Case Name Status Exec Time Memory
00_example_01.txt 12 ms 41216 KB
00_example_02.txt 12 ms 41216 KB
00_example_03.txt 12 ms 41216 KB
00_example_04.txt 287 ms 41216 KB
01.txt 12 ms 41216 KB
02.txt 110 ms 41216 KB
03.txt 328 ms 41216 KB
04.txt 57 ms 41216 KB
05.txt 12 ms 41216 KB
06.txt 21 ms 41216 KB
07.txt 12 ms 41216 KB
08.txt 121 ms 41216 KB
09.txt 284 ms 41216 KB
10.txt 58 ms 41216 KB
11.txt 274 ms 41216 KB
12.txt 297 ms 41216 KB
13.txt 281 ms 41216 KB
14.txt 290 ms 41216 KB
15.txt 276 ms 41216 KB
16.txt 305 ms 41216 KB
17.txt 324 ms 41216 KB
18.txt 296 ms 41216 KB
19.txt 317 ms 41216 KB
20.txt 329 ms 41216 KB
21.txt 331 ms 41216 KB
22.txt 14 ms 41216 KB
23.txt 12 ms 41216 KB
24.txt 321 ms 41216 KB
25.txt 347 ms 41216 KB
26.txt 323 ms 41216 KB
27.txt 12 ms 41216 KB
28.txt 126 ms 41216 KB
29.txt 273 ms 41216 KB
30.txt 299 ms 41216 KB
31.txt 284 ms 41216 KB
32.txt 297 ms 41216 KB
33.txt 295 ms 41216 KB
34.txt 274 ms 41216 KB
35.txt 307 ms 41216 KB
36.txt 13 ms 41216 KB
37.txt 15 ms 41216 KB
38.txt 12 ms 41216 KB
39.txt 263 ms 41216 KB