Submission #447950

#	Time	Username	Problem	Language	Result	Execution time	Memory
447950		kakayoshi	Knapsack (NOI18_knapsack)	C++14	73 / 100	313 ms	262148 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;
ll dp[2005],pre[2005][2005],n,S,v,w,k;
vector <ll > save[2005];
void solve()
{
    cin>>S>>n;
    forw(i,1,n)
    {
        cin>>v>>w>>k;
        forw(j,1,min(S/w,k))
            save[w].pb(v);
    }
    forw(i,1,S)
    if (save[i].size())
    {
        sort(all(save[i]),greater<ll>());
        ll length=save[i].size()-1;
        //cout<<i<<endl;
        forw(j,0,min(length,S))
        {
            //cout<<save[i][j]<<" ";
            pre[i][j+1]=pre[i][j]+save[i][j];
        }
        //cout<<endl;
    }
    forw(i,1,S)
    if (save[i].size())
    {
        forb(w,S,1)
            forw(k,0,save[i].size()-1)
            {
                if (w-i*(k+1)<0) break;
                dp[w]=max(dp[w],dp[w-i*(k+1)]+pre[i][k+1]);
            }
    }
    ll 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:7:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define forw(i,a,b) for (ll i=a;i<=b;i++)
......
   53 |             forw(k,0,save[i].size()-1)
      |                  ~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:53:13: note: in expansion of macro 'forw'
   53 |             forw(k,0,save[i].size()-1)
      |             ^~~~

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