Submission #1101617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101617		suraj517	Knapsack (NOI18_knapsack)	C++14	100 / 100	49 ms	7492 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define pdouble(x) fixed<<setprecision(20)<<x
#define inf 1e9
#define inff 1e18
#define vec vector
#define pii pair<int,int>
#define pll pair<long long,long long>
#define maxv(a) *max_element(a.begin(), a.end())
#define minv(a) *min_element(a.begin(), a.end())
#define pb push_back
#define ff first
#define ub upper_bound
#define lb lower_bound
#define ss second
#define YY cout << "YES" << endl
#define NN cout << "NO" << endl
#define C(x) cout << x << endl
#define f(i, a, b) for (int i = a; i < b; i++)
#define rf(i, a, b) for (int i = a - 1; i >= b; i--)
#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define all(x) x.begin(), x.end()
#define google(i, x) cout << "Case #" << i << ": " << x << endl
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

const ll M = 1e9+7;

ll gcd(ll a, ll b) { while (b) {a %= b; swap(a,b);} return a; }
ll lcm(ll a, ll b) { ll g=gcd(a,b); ll res=a*(b/g); return res; }
ll extended_gcd(ll a, ll b, ll &x, ll &y) { if (b==0) { x=1; y=0; return a; } ll x1,y1; ll g=extended_gcd(b,a%b,x1,y1); x=y1; y=x1-y1*(a/b); return g; }
ll binExp(ll a, ll b, ll m=M) { a = a % m; ll res = 1; while (b) { if (b&1) { res=(res * a) % m; } a=(a * a) % m; b>>=1; } return res; }
ll mod_inv(ll a, ll m=M) { a = a % m; return binExp(a,m-2,m); }     // only for prime m
ll mod_add(ll a, ll b, ll m=M) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
ll mod_sub(ll a, ll b, ll m=M) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
ll mod_mul(ll a, ll b, ll m=M) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
ll mod_div(ll a, ll b, ll m=M) { a = a % m; ll binv = mod_inv(b,m); return (((a*binv)%m)+m)%m; }
int test;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,1,-1};


void print(auto &a)
{
    for(auto it:a)
    {
        cout<<it<<" ";  
    }
    cout<<endl;
}

/****************************   C..O..D..E   ****************************/

const int N = 2e5+3; 


void solve()
{
    ll s,n; cin>>s>>n;
    map<ll,vec<pll>> mp;
    f(i,0,n)
    {
        ll v,w,k; cin>>v>>w>>k;
        mp[w].pb({v,k});
    }

    vec<ll> dp(s+3);
    for(auto it:mp)
    {
        vec<pll> a = it.ss;
        ll w = it.ff;
        sort(all(a), greater<pll>());
        ll id = 0;
        for(int i = 0; i*w < s; i++)
        {
            if(id >= a.size()) break;
            for(ll j = s; j >= w; j--)
            {
                
                dp[j] = max(dp[j], dp[j-w] + a[id].ff);
            }
            a[id].ss--;
            if(a[id].ss == 0) id++;
        }
    }
    C(dp[s]);
}   
 

int main()
{
    fast_io;
    // fun();
    int t = 1; 
    // cin>>t;
    test = 1;
    while(t--)
    {
        solve();
        test++;
    }
    return 0;
}

Compilation message (stderr)

knapsack.cpp:49:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   49 | void print(auto &a)
      |            ^~~~
knapsack.cpp: In function 'void solve()':
knapsack.cpp:82:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             if(id >= a.size()) break;
      |                ~~~^~~~~~~~~~~

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