이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "NOI18_knapsack"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int N = 1e5 + 1;
const int S = 2e3 + 1;
int s, n;
int v[N], w[N], k[N], a[N];
void enter(){
cin >> s >> n;
FORU(i, 1, n){
cin >> v[i] >> w[i] >> k[i];
a[i] = i;
}
sort(a + 1, a + n + 1, [&](const int &i, const int &j){
return v[i] * w[j] > v[j] * w[i];
}
);
}
ll dp[S][2];
void solve(){
FORU(i, 1, n){
// if(i != n - 1) assert(1LL * v[a[i]] * w[a[i + 1]] >= 1LL * v[a[i + 1]] * w[a[i]]);
FORU(j, 0, s){
if(j == 0 || dp[j][0]){
FORU(z, 1, k[a[i]]) if(j + z * w[a[i]] <= s){
dp[j + z * w[a[i]]][1] = max(dp[j + z * w[a[i]]][1], dp[j][0] + z * v[a[i]]);
} else break;
}
dp[j][0] = dp[j][1];
}
if(dp[s][1]) break;
}
ll ans = 0;
FORU(i, 0, s) ans = max(ans, dp[i][1]);
cout << ans;
}
int main(){
IOS;
Fi();
enter();
solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'void Fi()':
knapsack.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen(PROB".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen(PROB".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... |