Submission #1072749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072749		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	167 ms	7340 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define __builtin_popcount __builtin_popcountll
#define BIT(x, i) (((x)>> (i))& 1)
#define MASK(x) (1LL<< (x))
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define faster cin.tie(0)->ios_base::sync_with_stdio(false)

using namespace std;

const int max6 = 1e6;
const int max5 = 1e5;
const int max4 = 1e4;
const ll INF = 1e18;
const int maxsgt = 31 -__builtin_clz(max5) + 2;

void file()
{
    #define task ""
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
}


void prepare()
{

}

int n, s;
ll dp[107][2007];

struct note
{
    int val, w, num;
} a[max5 + 7];
void test()
{
    cin >> s >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].val >> a[i].w >> a[i].num;

    memset(dp, 0, sizeof(dp));

    ll ans = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= s; j++){
            dp[i][j] = dp[i - 1][j];
            for (int k = 1; k <= a[i].num; k++){
                if (j < a[i].w * k * 1ll) break;
                dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i].w * k] + a[i].val * k);
            }
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans;

}
signed main()
{
    faster;
    file();
    prepare();
    int numtest = 1, subtask;
    //cin >> numtest;
    //cin >> subtask;
    while(numtest--) test();
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:72:22: warning: unused variable 'subtask' [-Wunused-variable]
   72 |     int numtest = 1, subtask;
      |                      ^~~~~~~
knapsack.cpp: In function 'void file()':
knapsack.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27