Submission #58103

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
// Begin Header {{{
using namespace std;
#ifndef DEBUG
#define dump(...)
#endif
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define rep(i, n) for (intmax_t i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
constexpr size_t operator""_zu(unsigned long long value) { return value; };
constexpr intmax_t operator""_jd(unsigned long long value) { return value; };
constexpr uintmax_t operator""_ju(unsigned long long value) { return value; };
constexpr int INF = 0x3f3f3f3f;
constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd;
namespace moke {
template <class T> using MaxHeap = priority_queue<T, vector<T>, less<T>>;
template <class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
inline void input() {}
template <class Head, class... Tail> inline void input(Head&& head, Tail&&... tail) {
cin >> head;
input(forward<Tail>(tail)...);
}
inline void outs() { cout << "\n"; }
template <class Head, class... Tail> inline void outs(Head&& head, Tail&&... tail) {
cout << head << (sizeof...(tail) ? " " : "");
outs(forward<Tail>(tail)...);
}
template <class T> inline void outs(vector<T> &vec) {
for (auto &e : vec) cout << e << " \n"[&e == &vec.back()];
}
template <class T> inline void outs(vector<vector<T>> &df) {
for (auto &vec : df) outs(vec);
}
inline void outl() { cout << "\n"; }
template <class Head, class... Tail> inline void outl(Head&& head, Tail&&... tail) {
cout << head << (sizeof...(tail) ? "\n" : "");
outl(forward<Tail>(tail)...);
}
template <class T> inline void outl(vector<T> &vec) {
for (auto &e : vec) cout << e << "\n";
}
inline void outn() {}
template <class Head, class... Tail> inline void outn(Head&& head, Tail&&... tail) {
cout << head;
outn(forward<Tail>(tail)...);
}
template <class T> inline void outn(vector<T> &vec) {
for (auto &e : vec) cout << e;
}
template <class T> inline vector<T> make_v(const T &initValue, size_t sz) {
return vector<T>(sz, initValue);
}
template <class T, class... Args> inline auto make_v(const T &initValue, size_t sz, Args... args) {
return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}
template <class A, class B> inline bool chmax(A &a, const B &b) noexcept {
return b > a && (a = b, true);
}
template <class A, class B> inline bool chmin(A &a, const B &b) noexcept {
return b < a && (a = b, true);
}
template <class A, class B> inline common_type_t<A, B> min(const A &a, const B &b) noexcept {
return a < b ? a : b;
}
template <class A, class B, class... Args>
inline common_type_t<A, B, Args...> min(const A &a, const B &b, const Args&... args) noexcept {
return moke::min(a < b ? a : b, args...);
}
template <class A, class B> inline common_type_t<A, B> max(const A &a, const B &b) noexcept {
return a > b ? a : b;
}
template <class A, class B, class... Args>
inline common_type_t<A, B, Args...> max(const A &a, const B &b, const Args&... args) noexcept {
return moke::max(a > b ? a : b, args...);
}
template <class A, class B> inline common_type_t<A, B> diff(const A &a, const B &b) noexcept {
return a < b ? b - a : a - b;
}
} // namespace moke
// }}} End Header
namespace moke {
int main_() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
var(intmax_t, N, W);
vector<intmax_t> v(N), w(N);
rep(i, N) input(v[i], w[i]);
auto dp = make_v<intmax_t>(0, N + 1, W + 1);
rep(i, N) reps(weight, 0, W) {
chmax(dp[i + 1][weight], dp[i][weight]);
if (weight >= w[i]) {
chmax(dp[i][weight], dp[i][weight - w[i]] + v[i]);
chmax(dp[i + 1][weight], dp[i][weight - w[i]] + v[i]);
}
}
outl(dp[N][W]);
return 0;
}
} // namespace moke
signed main() { // {{{
moke::main_();
return 0;
} // }}}

ステータス

項目 データ
問題 0239 - ナップザック問題(Medium)
ユーザー名 もけ
投稿日時 2020-01-12 16:18:23
言語 C++14
状態 Accepted
得点 3
ソースコード長 4255 Byte
最大実行時間 42 ms
最大メモリ使用量 8788 KB

セット

セット 得点 Cases
1 ALL 3 / 3 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
DPL_1_C_in1.txt AC 42 ms 604 KB
1
DPL_1_C_in2.txt AC 20 ms 564 KB
1
DPL_1_C_in3.txt AC 41 ms 708 KB
1
DPL_1_C_in4.txt AC 23 ms 640 KB
1
DPL_1_C_in5.txt AC 24 ms 892 KB
1
DPL_1_C_in6.txt AC 26 ms 716 KB
1
DPL_1_C_in7.txt AC 22 ms 800 KB
1
DPL_1_C_in8.txt AC 25 ms 752 KB
1
DPL_1_C_in9.txt AC 24 ms 700 KB
1
DPL_1_C_in10.txt AC 26 ms 692 KB
1
DPL_1_C_in11.txt AC 20 ms 560 KB
1
DPL_1_C_in12.txt AC 20 ms 672 KB
1
DPL_1_C_in13.txt AC 21 ms 704 KB
1
DPL_1_C_in14.txt AC 20 ms 996 KB
1
DPL_1_C_in15.txt AC 22 ms 1592 KB
1
DPL_1_C_in16.txt AC 28 ms 2416 KB
1
DPL_1_C_in17.txt AC 23 ms 2604 KB
1
DPL_1_C_in18.txt AC 23 ms 448 KB
1
DPL_1_C_in19.txt AC 29 ms 1552 KB
1
DPL_1_C_in20.txt AC 18 ms 640 KB
1
DPL_1_C_in21.txt AC 21 ms 588 KB
1
DPL_1_C_in22.txt AC 24 ms 1444 KB
1
DPL_1_C_in23.txt AC 29 ms 2628 KB
1
DPL_1_C_in24.txt AC 30 ms 4768 KB
1
DPL_1_C_in25.txt AC 21 ms 4624 KB
1
DPL_1_C_in26.txt AC 24 ms 4612 KB
1
DPL_1_C_in27.txt AC 26 ms 752 KB
1
DPL_1_C_in28.txt AC 21 ms 804 KB
1
DPL_1_C_in29.txt AC 17 ms 844 KB
1
DPL_1_C_in30.txt AC 22 ms 1564 KB
1
DPL_1_C_in31.txt AC 23 ms 3148 KB
1
DPL_1_C_in32.txt AC 28 ms 4804 KB
1
DPL_1_C_in33.txt AC 23 ms 6784 KB
1
DPL_1_C_in34.txt AC 28 ms 8560 KB
1
DPL_1_C_in35.txt AC 28 ms 8608 KB
1
DPL_1_C_in36.txt AC 27 ms 8644 KB
1
DPL_1_C_in37.txt AC 28 ms 8688 KB
1
DPL_1_C_in38.txt AC 27 ms 8740 KB
1
DPL_1_C_in39.txt AC 28 ms 8788 KB
1
DPL_1_C_in40.txt AC 28 ms 8660 KB
1