Submission #2083670
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
∧_∧
∧_∧ (´<_` ) Welcome to My Coding Space!
( ´_ゝ`) / ⌒i
/ \ | |
/ / ̄ ̄ ̄ ̄/ |
__(__ニつ/ _/ .| .|____
\/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/
int N; ll X[20], C[20], V[20];
ll dp[20][1 << 18];
vector<pair<ll, ll>> v;
//---------------------------------------------------------------------------------------------------
ll memo[20][1 << 18];
ll f(int n, int msk) {
if (0 <= memo[n][msk]) return memo[n][msk];
if (n == N) return 0;
// 売却
ll sold = infl;
rep(i, 0, N) if (msk & (1 << i)) chmin(sold, f(n + 1, msk - (1 << i)));
// 購入
ll buy = dp[n][msk];
return memo[n][msk] = max(sold, buy);
}
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N;
rep(i, 0, N) cin >> X[i];
rep(i, 0, N) cin >> C[i];
rep(i, 0, N) cin >> V[i];
rep(n, 0, N + 1) {
ll yen = 0;
rep(i, 0, n) yen += X[i];
rep(msk, 0, 1 << N) {
ll co = 0, va = 0;
rep(i, 0, N) if (msk & (1 << i)) co += C[i], va += V[i];
if (co <= yen) dp[n][msk] = va;
else dp[n][msk] = 0;
}
rep(msk, 0, 1 << N) rep(i, 0, N) if (msk & (1 << i)) chmax(dp[n][msk], dp[n][msk ^ (1 << i)]);
}
rep(i, 0, N + 1) rep(msk, 0, 1 << N) memo[i][msk] = -1;
cout << f(0, (1 << N) - 1) << endl;
}
Submission Info
Submission Time |
|
Task |
C - 駆引取引 |
User |
hamayanhamayan |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
2532 Byte |
Status |
AC |
Exec Time |
595 ms |
Memory |
82176 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt |
All |
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 |
AC |
4 ms |
14592 KB |
00_example_02.txt |
AC |
3 ms |
10496 KB |
00_example_03.txt |
AC |
5 ms |
22784 KB |
00_example_04.txt |
AC |
584 ms |
82176 KB |
01.txt |
AC |
8 ms |
35072 KB |
02.txt |
AC |
285 ms |
72960 KB |
03.txt |
AC |
587 ms |
82176 KB |
04.txt |
AC |
138 ms |
68352 KB |
05.txt |
AC |
8 ms |
35072 KB |
06.txt |
AC |
37 ms |
59776 KB |
07.txt |
AC |
8 ms |
35072 KB |
08.txt |
AC |
275 ms |
72960 KB |
09.txt |
AC |
587 ms |
82176 KB |
10.txt |
AC |
134 ms |
68352 KB |
11.txt |
AC |
594 ms |
82176 KB |
12.txt |
AC |
585 ms |
82176 KB |
13.txt |
AC |
589 ms |
82176 KB |
14.txt |
AC |
583 ms |
82176 KB |
15.txt |
AC |
585 ms |
82176 KB |
16.txt |
AC |
593 ms |
82176 KB |
17.txt |
AC |
587 ms |
82176 KB |
18.txt |
AC |
584 ms |
82176 KB |
19.txt |
AC |
586 ms |
82176 KB |
20.txt |
AC |
585 ms |
82176 KB |
21.txt |
AC |
588 ms |
82176 KB |
22.txt |
AC |
16 ms |
51456 KB |
23.txt |
AC |
4 ms |
18688 KB |
24.txt |
AC |
588 ms |
82176 KB |
25.txt |
AC |
590 ms |
82176 KB |
26.txt |
AC |
583 ms |
82176 KB |
27.txt |
AC |
8 ms |
35072 KB |
28.txt |
AC |
282 ms |
72960 KB |
29.txt |
AC |
579 ms |
82176 KB |
30.txt |
AC |
595 ms |
82176 KB |
31.txt |
AC |
583 ms |
82176 KB |
32.txt |
AC |
594 ms |
82176 KB |
33.txt |
AC |
587 ms |
82176 KB |
34.txt |
AC |
586 ms |
82176 KB |
35.txt |
AC |
582 ms |
82176 KB |
36.txt |
AC |
16 ms |
51456 KB |
37.txt |
AC |
23 ms |
55680 KB |
38.txt |
AC |
10 ms |
43264 KB |
39.txt |
AC |
587 ms |
82176 KB |