제출 #735895

#제출 시각아이디문제언어결과실행 시간메모리
735895asdfgraceKnapsack (NOI18_knapsack)C++17
29 / 100
1 ms464 KiB
#include <bits/stdc++.h> using namespace std; #define DEBUG(x) //x #define A(x) DEBUG(assert(x)) #define PRINT(x) DEBUG(cerr << x) #define PV(x) DEBUG(cerr << #x << " = " << x << '\n') #define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n') #define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");) #define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");) typedef int64_t i64; const int INF = 1000000007; //998244353; struct T3 { i64 v; i64 w; i64 k; }; struct S { int s, n; vector<T3> a; void run() { cin >> s >> n; a.resize(n); for (int i = 0; i < n; ++i) { cin >> a[i].v >> a[i].w >> a[i].k; } sort(a.begin(), a.end(), [&](T3 &x, T3 &y) { if (x.w != y.w) return x.w < y.w; if (x.v != y.v) return x.v > y.v; return x.k < y.k; }); vector<i64> cur(s + 1, -1), prev(s + 1, -1), cnt(s + 1, 0); cur[0] = 0; prev[0] = 0; for (int i = 0; i < n; ++i) { PAR(prev); for (int j = 0; j + a[i].w <= s; ++j) { if (cur[j] == -1) continue; if (make_pair(cur[j + a[i].w], -cnt[j + a[i].w]) < make_pair(cur[j] + a[i].v, -cnt[j] - 1) && cnt[j] < a[i].k) { PRINT(' '); PV(j); cur[j + a[i].w] = cur[j] + a[i].v; cnt[j + a[i].w] = cnt[j] + 1; } else if (prev[j] != -1 && cur[j + a[i].w] < prev[j] + a[i].v) { PV(j); cur[j + a[i].w] = prev[j] + a[i].v; cnt[j + a[i].w] = 1; } } PAR(cur); PAR(cnt); prev = cur; fill(cnt.begin(), cnt.end(), 0); } i64 ans = 0; for (int i = 0; i <= s; ++i) { ans = max(ans, cur[i]); } cout << ans << '\n'; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); auto sol = make_unique<S>(); sol->run(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...