#include <bits/stdc++.h>
#define int long long int
#define mod 1000000007
#define inf (1LL << 60)
#define endl "\n"
//#define N 1e6 + 1
#define fast_io \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define all(x) begin(x), end(x)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define prec cout << fixed << setprecision(9);
using namespace std;
// Debugging starts
#define dbg(...) \
cout << "[" << #__VA_ARGS__ << "]: "; \
cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N>
int SIZE(const T (&t)[N])
{
return N;
}
template <typename T>
int SIZE(const T &t)
{
return t.size();
}
string to_string(const string s, int x1 = 0, int x2 = 1e9)
{
return '"' + ((x1 < s.size()) ? s.substr(x1, x2 - x1 + 1) : "") + '"';
}
string to_string(const char *s) { return to_string((string)s); }
string to_string(const bool b) { return (b ? "true" : "false"); }
string to_string(const char c) { return string({c}); }
template <size_t N>
string to_string(const bitset<N> &b, int x1 = 0, int x2 = 1e9)
{
string t = "";
for (int __iii__ = min(x1, SIZE(b)), __jjj__ = min(x2, SIZE(b) - 1);
__iii__ <= __jjj__; ++__iii__)
{
t += b[__iii__] + '0';
}
return '"' + t + '"';
}
template <typename A, typename... C>
string to_string(const A(&v), int x1 = 0, int x2 = 1e9, C... coords);
int l_v_l_v_l = 0, t_a_b_s = 0;
template <typename A, typename B>
string to_string(const pair<A, B> &p)
{
l_v_l_v_l++;
string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
l_v_l_v_l--;
return res;
}
template <typename A, typename... C>
string to_string(const A(&v), int x1, int x2, C... coords)
{
int rnk = rank<A>::value;
string tab(t_a_b_s, ' ');
string res = "";
bool first = true;
if (l_v_l_v_l == 0)
res += endl;
res += tab + "[";
x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v));
auto l = begin(v);
advance(l, x1);
auto r = l;
advance(r, (x2 - x1) + (x2 < SIZE(v)));
for (auto e = l; e != r; e = next(e))
{
if (!first)
{
res += ", ";
}
first = false;
l_v_l_v_l++;
if (e != l)
{
if (rnk > 1)
{
res += endl;
t_a_b_s = l_v_l_v_l;
};
}
else
{
t_a_b_s = 0;
}
res += to_string(*e, coords...);
l_v_l_v_l--;
}
res += "]";
if (l_v_l_v_l == 0)
res += endl;
return res;
}
void dbgm() { ; }
template <typename Heads, typename... Tails>
void dbgm(Heads H, Tails... T)
{
cout << to_string(H) << " | ";
dbgm(T...);
}
#define dbgm(...) \
cout << "[" << #__VA_ARGS__ << "]: "; \
dbgm(__VA_ARGS__); \
cout << endl
// debugging ends
//Read Templates Starts
template <typename T = int>
std::vector<std::vector<T>> ReadMatrix(int row_count = 0, int column_count = 0,
std::istream &in_stream = std::cin);
template <typename T = int>
std::vector<T> ReadArray(int size = 0, std::istream &in_stream = std::cin);
//Read Templates Ends
//Solve f(x) starts
void solve()
{
int knapsack, n, w;
cin >> knapsack >> n;
vector<int> values(n + 1), weights(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> values[i] >> weights[i] >> w;
int initialSum = 1, p = 2;
while (p < w)
{
if (initialSum + p <= knapsack)
{
initialSum += p;
weights.push_back(p * weights[i]);
values.push_back(p * values[i]);
}
p *= 2;
}
if (w - initialSum != 0)
{
weights.push_back((knapsack - initialSum) * weights[i]);
values.push_back((knapsack - initialSum) * values[i]);
}
}
// dbg(weights);
// dbg(values);
//Recalculating n after adding new weights
n = weights.size();
//vector<vector<int>> dp(n + 1, vector<int>(knapsack + 1, INT_MIN));
//dp[0][0] = 0;
int dp[knapsack + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = knapsack; j >= 0; j--) {
dp[j] = (weights[i] > j) ? dp[j] : max(dp[j], dp[j - weights[i]] + values[i]);
}
}
cout << dp[knapsack];
// for (int i = 1; i <= n; i++)
// {
// for (int j = 0; j <= knapsack; j++)
// {
// dp[i][j] = dp[i - 1][j];
// if (j >= weights[i - 1])
// {
// if (dp[i - 1][j - weights[i - 1]] != INT_MIN)
// {
// dp[i][j] = max(dp[i - 1][j - weights[i - 1]] + values[i - 1], dp[i][j]);
// }
// }
// }
// }
// // dbg(dp);
// int finalAns = INT_MIN;
// for (int i = 0; i <= knapsack; i++)
// {
// finalAns = max(dp[n][i], finalAns);
// }
// cout << finalAns << endl;
}
//Init Code
void init_code()
{
fast_io;
// freopen("feast.in", "r", stdin);
// freopen("feast.out", "w", stdout);
}
int32_t main()
{
init_code();
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
//Init Code Ends
template <typename T>
std::vector<T> ReadArray(int size, std::istream &in_stream)
{
if (!size)
{
in_stream >> size;
}
std::vector<T> array(size);
for (auto &element : array)
{
in_stream >> element;
}
return array;
}
template <typename T>
std::vector<std::vector<T>> ReadMatrix(int row_count, int column_count, std::istream &in_stream)
{
if (!row_count)
{
in_stream >> row_count >> column_count;
}
else if (!column_count)
{
column_count = row_count;
}
std::vector<std::vector<T>> matrix(row_count, std::vector<int>(column_count));
for (auto &row : matrix)
{
for (auto &entry : row)
{
in_stream >> entry;
}
}
return matrix;
}
Compilation message
knapsack.cpp: In function 'std::string to_string(std::string, long long int, long long int)':
knapsack.cpp:32:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | return '"' + ((x1 < s.size()) ? s.substr(x1, x2 - x1 + 1) : "") + '"';
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
