| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 585814 | imtiyazrasool92 | Knapsack (NOI18_knapsack) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O1")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#ifdef imtiyazrasool92
#include "algos/debug.h"
#else
#define dbg(...) 92
#endif
int S, N;
// int dp[100000][2001];
map<pair<int, int>, int> dp;
int A[100000][3];
int dfs(int index, int weight) {
if (weight == 0)
return 0;
if (index >= N)
return 0;
if (dp.find({index, weight}) == dp.end()) {
int answer = 0;
for (int i = 0; i <= min(weight / A[index][1], A[index][2]); i++) {
if (weight - (i * A[index][1]) >= 0)
answer = max(answer, dfs(index + 1, weight - (i * A[index][1])) + A[index][0] * i);
else
break;
}
dp[ {index, weight}] = answer;
}
return dp[ {index, weight}];
}
void run_case() {
cin >> S >> N;
for (int i = 0; i < N; i++) {
cin >> A[i][0] >> A[i][1] >> A[i][2];
if (A[i][1] > S) {
N--;
i--;
} else if (A[i][1] == 0) {
N--;
i--;
}
}
for (int i = 0; i < N; i++)
for (int s = 0; s <= S; s++)
dp[i][s] = -1;
cout << dfs(0, S);
}
int32_t main() {
ios::sync_with_stdio(false);
#ifndef imtiyazrasool92
cin.tie(nullptr);
#endif
int tests = 1;
// cin >> tests;
while (tests--) {
run_case();
cout << '\n';
}
return 0;
}