Submission #565297

#	Time	Username	Problem	Language	Result	Execution time	Memory
565297		NeriW	Knapsack (NOI18_knapsack)	C++17	49 / 100	1077 ms	1900 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, int> pill;
typedef vector<pill> vpill;
typedef vector<vpill> vvpill;
const ll inf = 1e18;
void update(int i, vll &T, int n, ll val)
{
    //cout << i << ", " << i + n-1 << ", " << T.size() << ";\n";
    i += n-1;
    T[i] = val;
    i/=2;
    for(; i > 0; i/=2)
    {
        T[i] = max(T[i*2], T[i*2+1]);
    }
}
int query(int l, int r, vll &T, int n)
{
    //cout << l << ", " << l + n-1 << ", " << T.size() << "; ";
    //cout << r << ", " << r + n-1 << ", " << T.size() << ";\n";
    l += n-1;
    r+= n-1;
    ll ans = 0;
    for(; l <= r; l >>= 1, r >>= 1)
    {
        if(l&1)
        {
            ans = max(T[l], ans);
            l++;
        }
        if(!(r&1))
        {
            ans = max(T[r], ans);
            r--;
        }
    }
    //cout << ans << " ans \n";
    return ans;
}
int main()
{
    //freopen("..\\io\\input.txt", "r", stdin);
    //freopen("..\\io\\output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int s, n; cin >> s >> n;
    vll k(n+1, 0);
    vll v(n+1, 0);
    vll w(n+1, 0);
    vvll dp(n+1, vll(s+1, 0));
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i] >> k[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int m = 0; m <= max(s - w[i]*k[i], w[i]); m++)
        {
            vll vals;
            for(int l = 0; l <= k[i] && m + l*w[i] <= s; l++)
            {
                vals.push_back(dp[i-1][m + l*w[i]] - v[i]*l);
            }
            int N = vals.size();
            int n1 = 1 << (32 - (__builtin_clz(N-1)));
            vll T(n1*2, 0);
            for(int p = 0; p < N; p++)
            {
                update(p+1, T, n1, vals[p]);
            }
            for(int l = 0; l <= k[i] && m + l*w[i] <= s; l++)
            {
                dp[i][m+w[i]*l] = max(query(1, l+1, T, n1) + v[i]*l, dp[i][m+w[i]*l]);
                /*f(i == 2)
                {
                    cout << m << ", " << l  << "; " << dp[i][m+w[i]*l] << ", " << m+w[i]*l <<  "\n";
                }*/
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i <= s; i++)
    {
        ans = max(ans, dp[n][i]);
    }
    /*for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= s; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }*/
    cout << ans << "\n";
}

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