Submission #2593735
Source Code Expand
#include <bits/stdc++.h> using namespace std; using lint = long long; using VL = vector<lint>; using VVL = vector<VL>; using P = pair<lint, lint>; signed main() { cin.tie(0); ios::sync_with_stdio(false); lint n, c; cin >> n >> c; VL v(n), w(n); for (int i = 0; i < n; i++) cin >> v[i] >> w[i]; if (*max_element(w.begin(), w.end()) <= 1000) { VVL dp(n + 1, VL(1000 * n + 1)); for (int i = 0; i < n; i++) { dp[i + 1] = dp[i]; for (int j = 1000 * n; j >= 0; j--) { if (j - w[i] < 0) break; dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]); } } cout << *max_element(dp[n].begin(), dp[n].begin() + c + 1) << '\n'; } else if(*max_element(v.begin(), v.end()) <= 1000) { VVL dp(n + 1, VL(1000 * n + 1, 9e18)); for (int i = 0; i <= n; i++) dp[i][0] = 0; for (int i = 0; i < n; i++) { dp[i + 1] = dp[i]; for (int j = 1000 * n; j >= 0; j--) { if (j - v[i] < 0) break; dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i]); } } for (int i = 1000 * n; i >= 0; i--) { if (dp[n][i] <= c) { cout << i << '\n'; break; } } } else { vector<P> vw1, vw2; for (int bit = 0; bit < 1 << n / 2; bit++) { P vw; for (int i = 0; i < n / 2; i++) { if (bit & 1 << i) { vw.first += v[i]; vw.second += w[i]; } } vw1.push_back(vw); } for (int bit = 0; bit < 1 << n - n / 2; bit++) { P vw; for (int i = n / 2; i < n; i++) { if (bit & 1 << i - n / 2) { vw.first += v[i]; vw.second += w[i]; } } vw2.push_back(vw); } auto comp = [](P a, P b) { return a.second > b.second or a.second == b.second and a.first > b.first; }; sort(vw2.begin(), vw2.end(), comp); for (int i = vw2.size() - 1; i > 0; i--) { vw2[i - 1].first = max(vw2[i - 1].first, vw2[i].first); } lint res = 0; for (auto&& vw : vw1) { auto itr = lower_bound(vw2.begin(), vw2.end(), P(9e18, c - vw.second), comp); if (itr == vw2.end()) continue; res = max(res, vw.first + (*itr).first); } cout << res << '\n'; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ナップサック問題 |
User | risujiroh |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2290 Byte |
Status | AC |
Exec Time | 252 ms |
Memory | 316160 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 34 / 34 | 33 / 33 | 33 / 33 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt |
Subtask1 | subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt |
Subtask2 | subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt |
Subtask3 | subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask00_sample_1.txt | AC | 1 ms | 384 KB |
subtask00_sample_2.txt | AC | 9 ms | 1528 KB |
subtask00_sample_3.txt | AC | 2 ms | 1152 KB |
subtask00_sample_4.txt | AC | 2 ms | 1152 KB |
subtask01_0.txt | AC | 9 ms | 1528 KB |
subtask01_1.txt | AC | 9 ms | 1528 KB |
subtask01_10.txt | AC | 9 ms | 1528 KB |
subtask01_11.txt | AC | 9 ms | 1528 KB |
subtask01_12.txt | AC | 9 ms | 1528 KB |
subtask01_13.txt | AC | 9 ms | 1528 KB |
subtask01_14.txt | AC | 9 ms | 1528 KB |
subtask01_2.txt | AC | 9 ms | 1528 KB |
subtask01_3.txt | AC | 9 ms | 1528 KB |
subtask01_4.txt | AC | 7 ms | 1528 KB |
subtask01_5.txt | AC | 7 ms | 7808 KB |
subtask01_6.txt | AC | 7 ms | 7808 KB |
subtask01_7.txt | AC | 9 ms | 1528 KB |
subtask01_8.txt | AC | 9 ms | 1528 KB |
subtask01_9.txt | AC | 9 ms | 1528 KB |
subtask02_0.txt | AC | 249 ms | 316160 KB |
subtask02_1.txt | AC | 246 ms | 316160 KB |
subtask02_10.txt | AC | 246 ms | 316160 KB |
subtask02_11.txt | AC | 246 ms | 316160 KB |
subtask02_12.txt | AC | 246 ms | 316160 KB |
subtask02_13.txt | AC | 247 ms | 316160 KB |
subtask02_14.txt | AC | 246 ms | 316160 KB |
subtask02_2.txt | AC | 246 ms | 316160 KB |
subtask02_3.txt | AC | 247 ms | 316160 KB |
subtask02_4.txt | AC | 246 ms | 316160 KB |
subtask02_5.txt | AC | 248 ms | 316160 KB |
subtask02_6.txt | AC | 246 ms | 316160 KB |
subtask02_7.txt | AC | 247 ms | 316160 KB |
subtask02_8.txt | AC | 247 ms | 316160 KB |
subtask02_9.txt | AC | 252 ms | 316160 KB |
subtask03_0.txt | AC | 247 ms | 316160 KB |
subtask03_1.txt | AC | 247 ms | 316160 KB |
subtask03_10.txt | AC | 247 ms | 316160 KB |
subtask03_11.txt | AC | 248 ms | 316160 KB |
subtask03_2.txt | AC | 246 ms | 316160 KB |
subtask03_3.txt | AC | 247 ms | 316160 KB |
subtask03_4.txt | AC | 246 ms | 316160 KB |
subtask03_5.txt | AC | 246 ms | 316160 KB |
subtask03_6.txt | AC | 247 ms | 316160 KB |
subtask03_7.txt | AC | 247 ms | 316160 KB |
subtask03_8.txt | AC | 247 ms | 316160 KB |
subtask03_9.txt | AC | 248 ms | 316160 KB |