Submission #7074706
Source Code Expand
// C - ナップサック問題
// template
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<long long, long long> LP;
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define REP_AB(i, a, b) for (ll i = ll(a); i <= ll(b); ++i)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)), v.end());
#define SIZE(x) ((ll)(x).size())
#define REVERSE(v) reverse(ALL(v))
// true / false
#define BIN_SEARCH(v, a) binary_search(ALL(v), a)
// index
#define BIN_LEFT(v, a) (lower_bound(ALL(v), a) - v.begin())
#define BIN_RIGHT(v, a) (upper_bound(ALL(v), a) - v.begin())
#define BIN_INSERT(v, a) (v.insert(v.begin() + BIN_LEFT(v, a), a))
#define DEL(v, i) v.erase(v.begin() + i)
#define INSERT(v, i, a) v.insert(v.begin() + i, a)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a / gcd(a, b)) * b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
#define out cout
#define in cin
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; }
// template end
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n, W;
in >> n >> W;
ll w[n+1] = {};
ll v[n+1] = {};
ll max_w = 0;
ll max_v = 0;
REP(i, n){
in >> v[i + 1] >> w[i + 1];
chmax(max_w, w[i+1]);
chmax(max_v, v[i+1]);
}
if(max_w <= 1000){
ll dp[n + 1][W + 1] = {};
REP_AB(i, 1, n){
REP_AB(j, 0, W){
dp[i][j] = dp[i-1][j];
if(j - 1 < 0) continue;
dp[i][j] = max(dp[i][j], dp[i][j-1]);
if(j-w[i] < 0) continue;
dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
}
}
out << dp[n][W] << endl;
}else if(max_v <= 1000){
ll sum_v;
REP(i, n+1){
sum_v += v[i+1];
}
ll dp[n+1][sum_v+1] = {};
REP(i, n+1) REP(j, sum_v+1) dp[i][j] = INF;
REP(i, n+1) dp[i][0] = 0;
REP_AB(i, 1, n){
REP(j, v[i]) dp[i][j] = dp[i-1][j];
REP_AB(j, v[i], sum_v){
// dp[n番目][価値jの時] = 価値をjにできる最小のw
dp[i][j] = dp[i-1][j];
if(dp[i-1][j-v[i]] > W) continue;
dp[i][j] = min(dp[i-1][j-v[i]] + w[i], dp[i][j]);
}
}
ll ans = 0;
REP(i, sum_v+1){
if(dp[n][i] <= W){
ans = i;
}
}
out << ans << endl;
}else{
// 半分全列挙
out << 0 << endl;
// ll a = int(n/2);
// ll b = n - a;
// REP(i, n+1){
// if(i < a){
// REP_AB(j, )
// }else{
// }
// }
}
}
Submission Info
Submission Time |
|
Task |
D - ナップサック問題 |
User |
bluexleoxgreen |
Language |
C++14 (GCC 5.4.1) |
Score |
33 |
Code Size |
3047 Byte |
Status |
RE |
Exec Time |
110 ms |
Memory |
146048 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
0 / 34 |
33 / 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 |
AC |
1 ms |
256 KB |
subtask00_sample_2.txt |
WA |
1 ms |
256 KB |
subtask00_sample_3.txt |
AC |
1 ms |
512 KB |
subtask00_sample_4.txt |
RE |
99 ms |
256 KB |
subtask01_0.txt |
WA |
1 ms |
256 KB |
subtask01_1.txt |
WA |
1 ms |
256 KB |
subtask01_10.txt |
WA |
1 ms |
256 KB |
subtask01_11.txt |
WA |
1 ms |
256 KB |
subtask01_12.txt |
WA |
1 ms |
256 KB |
subtask01_13.txt |
WA |
1 ms |
256 KB |
subtask01_14.txt |
WA |
1 ms |
256 KB |
subtask01_2.txt |
WA |
1 ms |
256 KB |
subtask01_3.txt |
WA |
1 ms |
256 KB |
subtask01_4.txt |
WA |
1 ms |
256 KB |
subtask01_5.txt |
AC |
1 ms |
256 KB |
subtask01_6.txt |
RE |
98 ms |
256 KB |
subtask01_7.txt |
WA |
1 ms |
256 KB |
subtask01_8.txt |
WA |
1 ms |
256 KB |
subtask01_9.txt |
WA |
1 ms |
256 KB |
subtask02_0.txt |
AC |
110 ms |
146048 KB |
subtask02_1.txt |
AC |
20 ms |
25088 KB |
subtask02_10.txt |
AC |
20 ms |
25088 KB |
subtask02_11.txt |
AC |
36 ms |
46464 KB |
subtask02_12.txt |
AC |
48 ms |
61824 KB |
subtask02_13.txt |
AC |
2 ms |
640 KB |
subtask02_14.txt |
AC |
10 ms |
10880 KB |
subtask02_2.txt |
AC |
86 ms |
114304 KB |
subtask02_3.txt |
AC |
19 ms |
23552 KB |
subtask02_4.txt |
AC |
88 ms |
116736 KB |
subtask02_5.txt |
AC |
8 ms |
9728 KB |
subtask02_6.txt |
AC |
72 ms |
95488 KB |
subtask02_7.txt |
AC |
47 ms |
61824 KB |
subtask02_8.txt |
AC |
20 ms |
25088 KB |
subtask02_9.txt |
AC |
74 ms |
97664 KB |
subtask03_0.txt |
RE |
98 ms |
256 KB |
subtask03_1.txt |
RE |
97 ms |
256 KB |
subtask03_10.txt |
RE |
96 ms |
256 KB |
subtask03_11.txt |
RE |
97 ms |
256 KB |
subtask03_2.txt |
RE |
98 ms |
256 KB |
subtask03_3.txt |
RE |
97 ms |
256 KB |
subtask03_4.txt |
RE |
98 ms |
256 KB |
subtask03_5.txt |
RE |
97 ms |
256 KB |
subtask03_6.txt |
RE |
100 ms |
256 KB |
subtask03_7.txt |
RE |
97 ms |
256 KB |
subtask03_8.txt |
RE |
97 ms |
256 KB |
subtask03_9.txt |
RE |
98 ms |
256 KB |