이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordt(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define forde(i, a, b) for (int i = (a), _b = (b); i > _b; --i)
#define trav(a, x) for (auto& a : x)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
using namespace __gnu_pbds;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef int64_t i64;
typedef pair<int,int> _ii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
constexpr int maxn=2e5+7;
constexpr i64 oo=1e9+7;
vector <i64> val[2007];
i64 dp[2007];
i64 s, n, v, w, k;
void solve() {
cin >> s >> n;
fort(i, 1, n) {
cin >> v >> w >> k;
i64 cur = 1;
while(cur <= k && cur * w <= s) {
val[cur * w].push_back(cur * v);
k -= cur; cur <<= 1;
}
mini(k, s / w);
if(k * w <= s) val[k * w].push_back(k * v);
}
fort(max_w, 1, s) {
sort(all(val[max_w]), greater<i64>());
trav(cur, val[max_w]) {
fordt(i, s, max_w) maxi(dp[i], dp[i - max_w] + cur);
}
}
cout << *max_element(dp + 1, dp + 1 + s);
}
#define NAME "test."
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if(fopen(NAME"inp", "r")) {
freopen(NAME"inp", "r", stdin);
freopen(NAME"out", "w", stdout);
}
int t=1;
while(t--) solve();
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'int main()':
knapsack.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | freopen(NAME"inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | freopen(NAME"out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |