Submission #5816238
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;
typedef unsigned long long ull;
static const ll INF = 1UL << 60;
static const int MAX_N = 200;
static const int MAX_N1 = 30;
static const int MAX_V = 1000;
ll N, W;
vector<ll> Value, Weight;
pair<ll, ll> ps[1 << (MAX_N1 / 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;
}*/
/*
map<ll,ll> ls[2];
void brute(int i,int end,ll wsum,ll vsum,int op){
if(i==end){
if(wsum<=W) ls[op][wsum]=max(ls[op][wsum],vsum);
return;
}
brute(i+1,end,wsum+Weight[i],vsum+Value[i],op);
brute(i+1,end,wsum,vsum,op);
}*/
void solve(){
//前半全列挙
int n2 = N / 2;//個数の真ん中くらいのn2個についてまず考える
for(int i = 0; i < 1 << n2; i++){//n2個のbit全探索
ll sw = 0, sv = 0;
for(int j = 0; j < n2; j++){
if(i >> j & 1){//j桁目のフラグが立っているか
sw += Weight[j];
sv += Value[j];
}
}
ps[i] = make_pair(sw, sv);//pair配列に突っ込む
}
//ムダな要素を省く
sort(ps, ps + (1 << n2));//n2桁分ps配列に突っ込んだのでとりあえずそこまでソート
int m = 1;//mは価値が上がった時に+1される。そうじゃなきゃ無視。
for(int i = 1; i < 1 << n2; i++){
if(ps[m-1].second < ps[i].second){
ps[m++] = ps[i];
}
}
//cout << m << endl;
//後ろ半分を全列挙し解を求める
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){//もし残りを足したswがW以下だったら、前半の中からいいものを見つける
ll tv = (lower_bound(ps, ps + m, make_pair(W - sw, INF)) - 1)->second;
//tvは重さW-sw、価値INFの次に大きいものの一つ前のイテレータについて価値を参照している
//つまり重さW-sw以下で価値最大のものの価値を示している
res = max(res, sv + 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();
/*brute(0,N/2,0,0,0);
brute(N/2,N,0,0,1);
ll ans=0;
deque<pair<ll,ll>> dq;
vector<pair<ll,ll>> vec;
for(auto it:ls[1]) vec.push_back(it);
reverse(vec.begin(),vec.end());//重い順に並び替え
//重い順にdequeに突っ込んでいって価値順に並べる
for(auto it:vec){
while(!dq.empty()&&dq.back().second<it.second){
dq.pop_back();
}
dq.push_back(it);
}
for(auto i:ls[0]){//ls[0]は軽い順に見る
ll curw=i.first,curv=i.second;
while(!dq.empty()&&curw+dq.front().first>W) dq.pop_front();
ans=max(ans,curv+dq.front().second);
}
cout<<ans<<endl;
return 0;*/
}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 dp[2][MAX_N * MAX_V + 1];//dp[i+1][j]:=i番目までの品物から価値の総和がjとなるように選んだ時の重さの総和の最小値
dp[0][0] = 0;
for(int i = 1; i < MAX_N * MAX_V; i++){
dp[0][i] = INF;
}
for(int i = 1; i <= N; i++){
for(int j = 0; j <= MAX_N * MAX_V; j++){
bool s = i % 2;
bool t = !s;
if(j - Value[i-1] >= 0){
dp[s][j] = min(dp[t][j], dp[t][j-Value[i-1]]+ Weight[i-1]);
//cout << "yes\n";
}
else {
dp[s][j] = dp[t][j];
//cout << "no\n";
}
}
}
int res = 0;
REP(i, MAX_N * MAX_V){
//cout << dp[N%2][i] << endl;
if(dp[N%2][i] <= W) {
res = i;
//cout << res << endl;
}
}
cout << res << endl;
//cout << INF << endl;
}
}
}
Submission Info
Submission Time |
|
Task |
A - 高橋君と青木君の好きな数 |
User |
raoZ |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5479 Byte |
Status |
WA |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt |
All |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample_01.txt |
WA |
1 ms |
256 KB |
subtask0_sample_02.txt |
WA |
1 ms |
256 KB |
subtask0_sample_03.txt |
WA |
1 ms |
256 KB |
subtask1_01.txt |
WA |
1 ms |
256 KB |
subtask1_02.txt |
WA |
1 ms |
256 KB |
subtask1_03.txt |
WA |
1 ms |
256 KB |
subtask1_04.txt |
WA |
1 ms |
256 KB |
subtask1_05.txt |
WA |
1 ms |
256 KB |
subtask1_06.txt |
WA |
1 ms |
256 KB |
subtask1_07.txt |
WA |
1 ms |
256 KB |
subtask1_08.txt |
WA |
1 ms |
256 KB |
subtask1_09.txt |
WA |
1 ms |
256 KB |
subtask1_10.txt |
WA |
1 ms |
256 KB |
subtask1_11.txt |
WA |
1 ms |
256 KB |
subtask1_12.txt |
WA |
1 ms |
256 KB |
subtask1_13.txt |
WA |
1 ms |
256 KB |
subtask1_14.txt |
WA |
1 ms |
256 KB |
subtask1_15.txt |
AC |
1 ms |
256 KB |