이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#ifdef VSLOCAL
#include "debug/d.h"
#endif
#ifdef LOCAL
#include "../../debug/d.h"
#endif
using namespace std;
using ll = long long;
using ld = long double;
#if defined(LOCAL) || defined(VSLOCAL)
#define dbg(...) line_info(__LINE__, #__VA_ARGS__), dbg1(__VA_ARGS__)
void nline() { cerr << '\n'; }
#else
#define dbg(...) 0
void nline() {}
#endif
struct item {
ll W, V, K;
bool operator< (const item that) const {
return (W == that.W) ? V > that.V : W < that.W;
}
};
ostream& operator<< (ostream& out, item i) {
out << "{" << i.V << ", " << i.W << ", " << i.K << "}";
return out;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("log.txt", "w", stderr);
#endif
int S, N;
cin >> S >> N;
vector<item> items (N);
for (int i = 0; i < N; ++i) {
cin >> items[i].V >> items[i].W >> items[i].K;
}
sort(items.begin(), items.end());
dbg(items);
vector<vector<ll>> value (S + 1, vector<ll> (S + 1));
vector<vector<ll>> dp (S + 1, vector<ll> (S + 1)); // maximum value
int index = 0;
for (int i = 1; i <= S; ++i) {
int count = 0;
dp[i] = dp[i - 1];
for (int j = i; j <= S; j += i) {
count++;
if (count > items[index].K) {
count = 1;
index++;
}
if (index >= N || items[index].W != i) break;
value[i][j] = value[i][j - i] + items[index].V;
for (int k = j; k <= S; ++k) {
// dp[i][k] = max(dp[i][k], dp[i - 1][k]);
dp[i][k] = max(dp[i][k], dp[i][k - 1]);
dp[i][k] = max(dp[i][k], dp[i - 1][k - j] + value[i][j]);
}
}
}
dbg(dp);
cout << dp[S][S] << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'int main()':
knapsack.cpp:19:18: warning: statement has no effect [-Wunused-value]
19 | #define dbg(...) 0
| ^
knapsack.cpp:52:5: note: in expansion of macro 'dbg'
52 | dbg(items);
| ^~~
knapsack.cpp:19:18: warning: statement has no effect [-Wunused-value]
19 | #define dbg(...) 0
| ^
knapsack.cpp:77:5: note: in expansion of macro 'dbg'
77 | dbg(dp);
| ^~~
# | 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... |