제출 #1280339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280339		huy_init	Knapsack (NOI18_knapsack)	C++17	37 / 100	2 ms	584 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

/*DEFINE*/
#define int long long
#define MASK(x) (1LL << (x))
#define all(x) x.begin(), x.end()
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
const int MOD = 1e9 + 7;

/*FUNTION*/
void ckmax(int &a, int b) { a = max(a, b); }
void ckmin(int &a, int b) { a = min(a, b); }
int gcd(int a, int b) { if (b==0) return a; return gcd(b, a%b); }
int lcm(int a, int b) { return a/gcd(a,b)*b; }
template<typename ...Args>
void logger(string vars, Args&&... values) 
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << '\n';
}
int binpow(int a, int b) 
{
    if (b == 0) return 1;
    int X = binpow(a, b / 2);
    if (b & 1) return X * X * a;
    return X * X;
}
struct item 
{
    int w, v, c;
};
struct v 
{
    int w, v;
};
signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);
    
    int t = 1;
    while (t--) 
    {
        // code here
        int n, s; cin >> s >> n;
        if (n == 1) 
        {
            cout << -1 << endl;
            return 0;
        }
        map<int, vector<pair<int, int>>> mp; 
        for (int i=0; i<n; i++) 
        {
            int w, v, k; cin >> v >> w >> k;
            mp[w].push_back({v, k});
        }
        vector<int> dp(s + 1, 0);
        for (int w=1; w<=s; w++) if (mp[w].size())
        {
            int need = s / w;
            sort(all(mp[w]));
            for (int i=mp[w].size() - 1; i>=0; i--) // LIST ĐỒ VẬT CÓ TRỌNG LƯỢNG LÀ w
            {
                int v = mp[w][i].first; // giá trị v
                int k = mp[w][i].second; // có k đồ vật trọng lượng w
                if (need >= k) 
                {
                    need -= k;
                    for (int i=1; i<=k; i++) 
                    {
                        for (int sum=s; sum>=w; sum--) 
                        {
                            ckmax(dp[sum], dp[sum - w] + v);
                        }
                    }
                }
                else 
                {
                    for (int i=1; i<=need; i++) 
                    {
                        for (int sum=s; sum>=w; sum--) 
                        {
                            ckmax(dp[sum], dp[sum - w] + v);
                        }
                    }
                    break;
                }
            }
        }
        int cost = 0;
        for (int i=0; i<=s; i++) 
        {
            ckmax(cost, dp[i]);
        }
        cout << cost << endl;
    }

    return 0; 
}

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