Submission #447962

#	Time	Username	Problem	Language	Result	Execution time	Memory
447962		kakayoshi	Knapsack (NOI18_knapsack)	C++14	100 / 100	68 ms	5008 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> data;
typedef pair<ll, pair<ll,ll> > super;
typedef vector <ll> vii;
#define forw(i,a,b) for (ll i=a;i<=b;i++)
#define forb(i,a,b) for (ll i=a;i>=b;i--)
#define fast {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=1e9+7;
const ll maxN=3e5+5;
const int tx[4]={0,0,1,-1};
const int ty[4]={1,-1,0,1};
const ll base=31;
int dp[2005],n,S,v,w,k;
vector <int> pre[2005];
vector<data> a[2005];
void solve()
{
    cin>>S>>n;
    forw(i,1,n)
    {
        cin>>v>>w>>k;
        a[w].pb({v,k});
    }
    forw(i,1,S)
    if (a[i].size())
    {
        sort(all(a[i]),greater<data>());
        pre[i].pb(0);
        int index=0;
       // cout<<i<<endl;
        forw(j,0,S/i)
        {
            if (index==a[i].size()) break;
            pre[i].pb(pre[i][j]+a[i][index].fi);
            //cout<<a[i][index].fi<<" ";
            a[i][index].se--;
            if (!a[i][index].se) index++;
        }
        //cout<<pre[i].size()<<endl;
        //cout<<endl;
    }
    forw(i,1,S)
    if (pre[i].size())
    {
        forb(w,S,1)
            forw(k,0,pre[i].size()-2)
            {
                if (w-i*(k+1)<0) break;
                dp[w]=max(dp[w],dp[w-i*(k+1)]+pre[i][k+1]);
            }
    }
    int ans=0;
    forw(i,1,S)
        ans=max(ans,dp[i]);
    cout<<ans;
}
int main()
{
    fast;
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    int t=1; //cin>>t;
    while (t--)
        solve();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if (index==a[i].size()) break;
      |                 ~~~~~^~~~~~~~~~~~~
knapsack.cpp:7:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define forw(i,a,b) for (ll i=a;i<=b;i++)
......
   58 |             forw(k,0,pre[i].size()-2)
      |                  ~~~~~~~~~~~~~~~~~~~
knapsack.cpp:58:13: note: in expansion of macro 'forw'
   58 |             forw(k,0,pre[i].size()-2)
      |             ^~~~

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