Submission #1023685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023685		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	1096 ms	1372 KiB

knapsack

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define vec vector
#define code signed main()
template<typename _T>
bool chmax(_T &a, const _T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}
code
{
	io();
    int n , m;
    int mx = 0;
    cin >> m >> n;
    vec<int>  dp(m + 1 , 0);
    for (int i = 1; i <= n; i++){
		int v , w , k;
		cin >> v >> w >> k;
		for (int x = 1; k > 0; x <<= 1){
			int	kol = min(k , x);
			k -= kol;
			int val = v * kol;
			int wei = w * kol;
			if (kol != 0 and wei != 0)
			for (int j = m; j >= wei; j--)
				chmax(dp[j] , dp[j - wei] + val) , chmax(mx , dp[j]);
		}
	}
    cout << mx << "\n";
    return 0;
}

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