Submission #848024

#	Time	Username	Problem	Language	Result	Execution time	Memory
848024		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	161 ms	34772 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>y.v) || (x.w==y.w && x.v==y.v && x.k>y.k) );
}
ll cntk[maxN+1];
ll dp[maxN+1];
map <ll,map<ll,ll> > mp,findkey;
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];
    ll cntcnt=1;
    for(ll i=1;i<=n;i++)
    {
        ll lmao1,lmao2,lmao3;
        cin>>lmao1>>lmao2>>lmao3;
        if(mp[lmao1][lmao2]==0)
        {
            a[i].v=lmao1;
            a[i].w=lmao2;
            a[i].k=lmao3;
            findkey[lmao1][lmao2]=i;
            mp[lmao1][lmao2]+=a[i].k;
        }
        else
        {
            mp[lmao1][lmao2]+=lmao3;
            a[findkey[lmao1][lmao2]].k+=lmao3;
            cntcnt++;
            a[i].v=cntcnt;
            a[i].w=inf;
            a[i].k=-inf;
        }
//        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;
        if(w==inf)
            continue;
        ll temp=s/w;
        if(cntk[w]<temp)
        {
            ll lmao=cntk[w];
            lmao+=k;
            if(lmao<=temp)
            {
                cntk[w]=lmao;
                while(k--)
                    items.push_back({v,w});
            }
            else
            {
                lmao=temp-cntk[w];
                cntk[w]=temp;
                while(lmao--)
                    items.push_back({v,w});
            }
        }
    }
//    for(ll i=1;i<=n;i++)
//        cout<<a[i].w<<" "<<a[i].v<<" "<<a[i].k<<endl;
//    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;
}

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