Submission #1145370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145370		ryanarokx	Knapsack (NOI18_knapsack)	C++20	100 / 100	111 ms	1884 KiB

knapsack

#include <bits/stdc++.h>
//#define int long long
#define ii pair<int,int>
#define x first
#define y second
#define SYNC ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lef (idx*2)+1
#define rig (idx*2)+2
#define mid (l+r)/2
#define MAX 2003

using namespace std;


int32_t main()
{
    /*
    for(int i=2000;i<=10000000;i*=10)
    {
        int s=0;
        for(int j=1;j<=i;j++)
            s+=i/j;
        cout<<i<<" "<<s<<" "<<s/i<<" "<< log2(i)<<endl;
    }
    */

    int s, n;
    cin >> s >> n;
    vector<int> v;
    vector<int> w;
    //vector<int> k;
    vector<vector<ii>> vp(MAX, vector<ii>());
    for(int i=1;i<=n;i++)
    {
        int ww, vv, kk;
        cin >> vv >> ww >> kk;
        vp[ww].push_back({-vv,kk});
    }
    for(int i=1;i<MAX;i++)
    {
        sort(vp[i].begin(),vp[i].end());
        int mx = MAX/i;
        for(int j=0;j<vp[i].size();j++)
        {
            while(vp[i][j].y && mx)
            {
                v.push_back(-vp[i][j].x);
                w.push_back(i);
                vp[i][j].y--;
                mx--;
            }
            if(mx<=0) break;
        }
    }
    int dp[2][s+1];
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<=s;j++)
            dp[i][j]=0;
    }
    for(int i=0;i<v.size();i++)
    {
        //k = min(k, MAX);
        for(int j=0;j<=s;j++)
        {
            //NOT TAKE
            int nt = dp[(i+1)%2][j];
            //TAKE
            int m = 1;// = min(k, j/w);
            int t = 0;
            //for(m=0;m<=k;m++)
            {
                if(j>=m*w[i])
                    t = dp[(i+1)%2][j-m*w[i]]+v[i]*m;
                //cout << t<< " - "<<nt<<" "<<m <<" "<<j<<" "<<w<<" "<<i<<endl;
                dp[i%2][j] = max(dp[i%2][j],max(nt, t));
            }
        }
        //for(int j=0;j<=s;j++)
            //cout << dp[i%2][j]<<" ";
        //cout<<endl;
    }
    cout << dp[(v.size()+1)%2][s];
    return 0;
}

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