Submission #848021

#	Time	Username	Problem	Language	Result	Execution time	Memory
848021		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	159 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
typedef long long ll;
#define endl "\n"
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
const ll maxN=1e6+1;
const ll mo=1e9+7;
const ll inf=1e15;
struct kool
{
    ll v,w,k;
};
bool cmp(kool x,kool y)
{
    return ( (x.w<y.w) || (x.w==y.w && x.v>x.v) || (x.w==y.w && x.v==y.v && x.k>=y.k) );
}
ll cntk[maxN+1];
ll dp[maxN+1];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll n,s;
    cin>>s>>n;
    kool a[n+1];
    for(ll i=1;i<=n;i++)
        cin>>a[i].v>>a[i].w>>a[i].k;
    sort(a+1,a+n+1,cmp);
    vector<pii> items;
    for(ll i=1;i<=n;i++)
    {
        ll v=a[i].v;
        ll w=a[i].w;
        ll k=a[i].k;
        ll temp=s/w;
        if(cntk[w]<temp)
        {
            ll lmao=cntk[w];
            lmao+=k;
            if(lmao<=temp)
            {
                while(k--)
                    items.push_back({v,w});
            }
            else
            {
                lmao=temp-cntk[w];
                while(lmao--)
                    items.push_back({v,w});
            }
        }
    }
//    cout<<endl;
//    for(auto i:items)
//        cout<<i.fi<<" "<<i.se<<endl;
    for(auto i:items)
    {
        for(ll j=s;j>=i.se;j--)
            dp[j]=max(dp[j],dp[j-i.se]+i.fi);
//        for(ll j=1;j<=s;j++)
//            cout<<dp[j]<<" ";
//        cout<<endl;
    }
    ll ans=-inf;
    for(ll i=0;i<=s;i++)
        ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'bool cmp(kool, kool)':
knapsack.cpp:17:43: warning: self-comparison always evaluates to false [-Wtautological-compare]
   17 |     return ( (x.w<y.w) || (x.w==y.w && x.v>x.v) || (x.w==y.w && x.v==y.v && x.k>=y.k) );
      |                                        ~~~^~~~

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