Submission #847770

#	Time	Username	Problem	Language	Result	Execution time	Memory
847770		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	1040 ms	36552 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i, a) for (int i=0; i<(a); i++)
#define all(x) x.begin(), x.end()
#define gcd __gcd
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
//const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};

const int N = 2001;
int dp[N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int s, n; cin >> s >> n;
    vector<pii> vec;
    while(n--){
        int v, w, a; cin >> v >> w >> a;
        for(int i = 0; i <= 30; ++i){
            if(a >= (1 << i)){
                a -= (1 << i);
                vec.emplace_back(w * (1 << i), v * (1 << i));
            }
        }
        for(int i = 0; i <= 30; ++i)
            if(a & (1 << i))
                vec.emplace_back(w * (1 << i), v * (1 << i));
    }
    memset(dp, -1, sizeof dp);
    dp[0] = 0;
    for(pii &it : vec){
        for(int j = s; j >= it.fi; --j)
            if(dp[j - it.fi] != -1)
                dp[j] = max(dp[j], dp[j - it.fi] + it.se);
    }
    cout << *max_element(dp, dp + s + 1);
    return 0;
}

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