Submission #6906956
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
bool isOK(int index, long long key, const vector<pair<long long, long long>> &v) {
return v.at(index).first <= key;
}
int binary_search(long long key, const vector<pair<long long, long long>> &v) {
int ng = (int)v.size();
int ok = 0;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (isOK(mid, key, v)) ok = mid;
else ng = mid;
}
return ok;
}
int main() {
int n, max_w;
cin >> n >> max_w;
vector<long long> v(n), w(n);
bool w_lower_1000 = true;
for (int i = 0; i < n; i++) {
cin >> v.at(i) >> w.at(i);
if (w.at(i) > 1000) w_lower_1000 = false;
}
if (n <= 30) {
if (n > 20) {
vector<pair<long long, long long>> groupA(0);
for (int bit = 0; bit <= (1 << 15) - 1; bit++) {
long long sum_w = 0, sum_v = 0;
for (int i = 0; i < 15; i++) {
if (bit & (1 << i)) {
sum_w += w.at(i);
sum_v += v.at(i);
}
}
groupA.push_back(make_pair(sum_w, sum_v));
}
vector<pair<long long, long long>> groupB(0);
for (int bit = 0; bit <= (1 << (n - 15)) - 1; bit++) {
long long sum_w = 0, sum_v = 0;
for (int i = 0; i < n - 15; i++) {
if ((bit << 15) & ((1 << i) << 15)) {
sum_w += w.at(i + 15);
sum_v += v.at(i + 15);
}
}
groupB.push_back(make_pair(sum_w, -sum_v));
}
sort(groupB.begin(), groupB.end());
long long m = 0;
for (int i = 0; i < (int)groupB.size(); i++) {
m = max(m, -groupB.at(i).second);
groupB.at(i).second = m;
}
long long ans = 0;
for (int i = 0; i < (int)groupA.size(); i++) {
if (groupA.at(i).first > max_w) continue;
int index = binary_search(max_w - groupA.at(i).first, groupB);
long long sum = groupA.at(i).second + groupB.at(index).second;
ans = max(ans, sum);
}
cout << ans << endl;
}
else {
long long ans = 0;
for (int bit = 0; bit < (1 << n) - 1; bit++) {
long long sum_w = 0, sum_v = 0;
for (int i = 0; i < n; i++) {
if (bit & (1 << i)) {
sum_w += w.at(i);
sum_v += v.at(i);
}
}
if (sum_w <= max_w) ans = max(ans, sum_v);
}
cout << ans << endl;
}
}
else if (w_lower_1000) {
vector<vector<long long>> dp(n + 1, vector<long long>(1000 * n + 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j <= 1000 * n; j++) {
dp.at(i + 1).at(j) = dp.at(i).at(j);
if (j - w.at(i) >= 0) dp.at(i + 1).at(j) = max(dp.at(i + 1).at(j), dp.at(i).at(j - w.at(i)) + v.at(i));
}
}
cout << dp.at(n).at(1000 * n) << endl;
}
else {
const long long INF = 1ll << 60;
vector<vector<long long>> dp(n + 1, vector<long long>(1000 * n + 1, INF));
dp.at(0).at(0) = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= 1000 * n; j++) {
dp.at(i + 1).at(j) = dp.at(i).at(j);
if (j - v.at(i) >= 0 && dp.at(i).at(j - v.at(i)) < INF) dp.at(i + 1).at(j) = min(dp.at(i + 1).at(j), dp.at(i).at(j - v.at(i)) + w.at(i));
}
}
long long ans = 0;
for (long long i = 0; i <= 1000 * n; i++) {
if (dp.at(n).at(i) <= max_w) ans = max(ans, i);
}
cout << ans << endl;
}
}
Submission Info
Submission Time |
|
Task |
D - ナップサック問題 |
User |
karyo |
Language |
C++14 (GCC 5.4.1) |
Score |
67 |
Code Size |
4067 Byte |
Status |
WA |
Exec Time |
311 ms |
Memory |
316160 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
34 / 34 |
0 / 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 |
256 KB |
subtask00_sample_2.txt |
AC |
8 ms |
1528 KB |
subtask00_sample_3.txt |
AC |
1 ms |
256 KB |
subtask00_sample_4.txt |
AC |
1 ms |
256 KB |
subtask01_0.txt |
AC |
8 ms |
1528 KB |
subtask01_1.txt |
AC |
8 ms |
1528 KB |
subtask01_10.txt |
AC |
8 ms |
1528 KB |
subtask01_11.txt |
AC |
8 ms |
1528 KB |
subtask01_12.txt |
AC |
8 ms |
1528 KB |
subtask01_13.txt |
AC |
8 ms |
1528 KB |
subtask01_14.txt |
AC |
8 ms |
1528 KB |
subtask01_2.txt |
AC |
8 ms |
1528 KB |
subtask01_3.txt |
AC |
8 ms |
1528 KB |
subtask01_4.txt |
AC |
7 ms |
1528 KB |
subtask01_5.txt |
AC |
10 ms |
1528 KB |
subtask01_6.txt |
AC |
7 ms |
1528 KB |
subtask01_7.txt |
AC |
8 ms |
1528 KB |
subtask01_8.txt |
AC |
8 ms |
1528 KB |
subtask01_9.txt |
AC |
8 ms |
1528 KB |
subtask02_0.txt |
WA |
291 ms |
316160 KB |
subtask02_1.txt |
WA |
291 ms |
316160 KB |
subtask02_10.txt |
WA |
291 ms |
316160 KB |
subtask02_11.txt |
WA |
291 ms |
316160 KB |
subtask02_12.txt |
WA |
290 ms |
316160 KB |
subtask02_13.txt |
AC |
311 ms |
316160 KB |
subtask02_14.txt |
WA |
291 ms |
316160 KB |
subtask02_2.txt |
WA |
291 ms |
316160 KB |
subtask02_3.txt |
WA |
292 ms |
316160 KB |
subtask02_4.txt |
WA |
291 ms |
316160 KB |
subtask02_5.txt |
WA |
290 ms |
316160 KB |
subtask02_6.txt |
WA |
291 ms |
316160 KB |
subtask02_7.txt |
WA |
290 ms |
316160 KB |
subtask02_8.txt |
WA |
290 ms |
316160 KB |
subtask02_9.txt |
WA |
292 ms |
316160 KB |
subtask03_0.txt |
AC |
246 ms |
316160 KB |
subtask03_1.txt |
AC |
244 ms |
316160 KB |
subtask03_10.txt |
AC |
245 ms |
316160 KB |
subtask03_11.txt |
AC |
238 ms |
316160 KB |
subtask03_2.txt |
AC |
245 ms |
316160 KB |
subtask03_3.txt |
AC |
245 ms |
316160 KB |
subtask03_4.txt |
AC |
245 ms |
316160 KB |
subtask03_5.txt |
AC |
245 ms |
316160 KB |
subtask03_6.txt |
AC |
245 ms |
316160 KB |
subtask03_7.txt |
AC |
245 ms |
316160 KB |
subtask03_8.txt |
AC |
244 ms |
316160 KB |
subtask03_9.txt |
AC |
246 ms |
316160 KB |