Submission #5805222
Source Code Expand
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; i++)
#define RREP(i,n) for(int i = n-1; i >= 0; i--)
using namespace std;
typedef long long ll;
static const ll INF = 1 << 21;
ll N, W;
vector<ll> Value, Weight;
pair<ll, ll> ps[1 << (30/2)]; //重さ、価値
/*
ll rec(int point, ll v, ll w){
if(point >= N){
return v;
}else{
if(w + Weight[point] > W) return rec(point+1,v,w);
else{
return max(rec(point+1, v, w), rec(point+1,v + Value[point], w + Weight[point]));
}
}
return 0;
}*/
void solve(){
//前半全列挙
int n2 = N / 2;
for(int i = 0; i < 1 << n2; i++){
ll sw = 0, sv = 0;
for(int j = 0; j < n2; j++){
if(i >> j & 1){
sw += Weight[j];
sv += Value[j];
}
}
ps[i] = make_pair(sw,sv);
}
//ムダな要素を省く
sort(ps, ps + (1 << n2));
int m = 1;
for(int i = 1; i < 1 << n2; i++){
if(ps[m-1].second < ps[i].second){
ps[m++] = ps[i];
}
}
//後ろ半分を全列挙し解を求める
ll res = 0;
for(int i = 0; i < 1 << (N - n2); i++){
ll sw = 0, sv = 0;
for(int j = 0; j < N - n2; j++){
if(i >> j & 1){
sw += Weight[n2 + j];
sv += Value[n2 + j];
}
}
if(sw <= W){
ll tv = (lower_bound(ps, ps + m, make_pair(W - sw, INF)) - 1)->second;
res = max(res, sw + tv);
}
}
printf("%lld\n", res);
}
int main(){
cin >> N >> W;
REP(i,N){
int v, w;
cin >> v >> w;
Value.push_back(v);
Weight.push_back(w);
}
if(N <= 30){
//cout << rec(0,0,0) << endl;//これだとWがデカイ時にあかん。
solve();
}else{
bool flag = 1;
REP(i,N){
if(Weight[i] >1000 || Weight[i] < 0) flag = 0;
}
if(flag){//weight1000以下
ll dpw[1001] = {0};//重さw以下で最大の価値
REP(i,N){
RREP(j, W+1){
if(j-Weight[i] >= 0) dpw[j] = max(dpw[j], dpw[j-Weight[i]] + Value[i]);
}
}
cout << dpw[W] << endl;
}else{//value 1000以下
ll dpv[200001] = {0};//価値v以上で最小の重さ
REP(i,N){
RREP(j, 200001){
if(j-Value[i] >= 0) dpv[j] = min(dpv[j], dpv[j-Value[i]] + Weight[i]);
}
}
REP(i, 200001){
if(dpv[i] > W){
cout << dpv[i-1] << endl;
break;
}
}
}
}
}
Submission Info
Submission Time |
|
Task |
D - ナップサック問題 |
User |
raoZ |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2833 Byte |
Status |
WA |
Exec Time |
49 ms |
Memory |
1792 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
0 / 34 |
0 / 33 |
0 / 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 |
WA |
1 ms |
256 KB |
subtask00_sample_2.txt |
WA |
7 ms |
768 KB |
subtask00_sample_3.txt |
WA |
1 ms |
256 KB |
subtask00_sample_4.txt |
WA |
1 ms |
256 KB |
subtask01_0.txt |
WA |
6 ms |
768 KB |
subtask01_1.txt |
WA |
7 ms |
768 KB |
subtask01_10.txt |
WA |
6 ms |
768 KB |
subtask01_11.txt |
WA |
7 ms |
768 KB |
subtask01_12.txt |
WA |
7 ms |
768 KB |
subtask01_13.txt |
WA |
7 ms |
768 KB |
subtask01_14.txt |
WA |
6 ms |
768 KB |
subtask01_2.txt |
AC |
6 ms |
768 KB |
subtask01_3.txt |
WA |
7 ms |
768 KB |
subtask01_4.txt |
AC |
6 ms |
768 KB |
subtask01_5.txt |
WA |
6 ms |
768 KB |
subtask01_6.txt |
WA |
6 ms |
768 KB |
subtask01_7.txt |
WA |
7 ms |
768 KB |
subtask01_8.txt |
WA |
7 ms |
768 KB |
subtask01_9.txt |
WA |
6 ms |
768 KB |
subtask02_0.txt |
AC |
26 ms |
1024 KB |
subtask02_1.txt |
AC |
6 ms |
384 KB |
subtask02_10.txt |
AC |
6 ms |
384 KB |
subtask02_11.txt |
AC |
9 ms |
512 KB |
subtask02_12.txt |
AC |
12 ms |
512 KB |
subtask02_13.txt |
AC |
1 ms |
256 KB |
subtask02_14.txt |
AC |
3 ms |
256 KB |
subtask02_2.txt |
AC |
21 ms |
768 KB |
subtask02_3.txt |
AC |
5 ms |
384 KB |
subtask02_4.txt |
AC |
21 ms |
896 KB |
subtask02_5.txt |
AC |
3 ms |
256 KB |
subtask02_6.txt |
AC |
18 ms |
768 KB |
subtask02_7.txt |
AC |
12 ms |
512 KB |
subtask02_8.txt |
AC |
6 ms |
384 KB |
subtask02_9.txt |
AC |
18 ms |
768 KB |
subtask03_0.txt |
WA |
49 ms |
1792 KB |
subtask03_1.txt |
WA |
49 ms |
1792 KB |
subtask03_10.txt |
WA |
49 ms |
1792 KB |
subtask03_11.txt |
WA |
49 ms |
1792 KB |
subtask03_2.txt |
WA |
49 ms |
1792 KB |
subtask03_3.txt |
WA |
49 ms |
1792 KB |
subtask03_4.txt |
WA |
49 ms |
1792 KB |
subtask03_5.txt |
WA |
49 ms |
1792 KB |
subtask03_6.txt |
WA |
49 ms |
1792 KB |
subtask03_7.txt |
WA |
49 ms |
1792 KB |
subtask03_8.txt |
WA |
49 ms |
1792 KB |
subtask03_9.txt |
WA |
49 ms |
1792 KB |