Submission #1064222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064222		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	1028 ms	17452 KiB

knapsack

//------------------------------------\
//   ------------------------------   \
//  |    created by Pham Phuongg   |  \
//  |       phamvuphuong2008       |  \
//  |     THPT CHUYEN HA TINH      |  \
//  |      HA TINH, VIET NAM       |  \
//  |    Bé Phương from TK4-CHT    |  \
//   ------------------------------   \
//------------------------------------\

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<int,ii>
using namespace std;
const int maxn = 1e6 + 5;
int n, s, dp[maxn], w, N, v, a;
vector<int> A, B;
main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  
   	cin >> s >> n;
    A.pb(0); B.pb(0);
    for (int i = 1; i <= n; i++) {
    	cin >> v >> w >> a;
    	int pow2 = 1;
//    	cout << v << " " << w << " " << a << endl;
    	while(a >= pow2) {
    		a -= pow2;
    		A.pb(w * pow2);
    		B.pb(v * pow2);
    		pow2 *= 2;
    	}
    	if (a > 0) {
    		A.pb(w * a);
    		B.pb(v * a);
    	}
    }
    N = A.size()-1;
//    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
    	for (int j = s; j >= 0; j--) {
    		if (j >= A[i]) dp[j] = max(dp[j], dp[j-A[i]] + B[i]);
    	}
    }
    cout << dp[s];
}

Compilation message (stderr)

knapsack.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //------------------------------------\
      | ^
knapsack.cpp:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 | main() {
      | ^~~~

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