이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int , int>
#define v first
#define k second
#define inf (int) (1e9 + 7)
signed main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL);
int n , m; cin >> m >> n;
vector<ii> a[m + 1];
for (int i = 1 ; i <= n ; i++) {
int v , w , k; cin >> v >> w >> k;
a[w].push_back(ii(v , k));
}
vector<int> dp;
dp.assign(m + 1 , -1);
dp[0] = 0;
for (int i = 1 ; i <= m ;i ++) {
if (!a[i].size()) continue;
vector<int> f;
f.assign(m + 1 , 0);
sort(a[i].begin() , a[i].end() , greater<ii>());
for (int j = i ; j <= m ; j++) {
int cnt , sum , pos , total;
cnt = sum = pos = total = 0;
while (cnt <= j/i && pos < a[i].size()) {
if (cnt + a[i][pos].k > j/i) {
int x = i*(j/i - cnt);
sum += x;
if (dp[j - sum] != -1)
f[j] = max({f[j] , dp[j - sum] + total + a[i][pos].v*(j/i - cnt)});
break;
}
else {
int x = i*a[i][pos].k;
sum += x;
cnt += a[i][pos].k;
total += a[i][pos].k*a[i][pos].v;
if (dp[j - sum] != -1)
f[j] = max({f[j] , dp[j - sum] + total});
pos++;
}
}
}
for (int j = i ; j <= m ; j++) {
dp[j] = max(dp[j] , f[j]);
}
}
int ans = 0;
for (int i = 0 ; i <= m ; i++) {
ans = max(ans , dp[i]);
//cerr << dp[i] << " ";
}
cout << ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'int main()':
knapsack.cpp:31:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | while (cnt <= j/i && pos < a[i].size()) {
| ~~~~^~~~~~~~~~~~~
# | 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... |