Submission #723782

#	Time	Username	Problem	Language	Result	Execution time	Memory
723782		Yagnik_Dhameliya	Knapsack (NOI18_knapsack)	C++14	100 / 100	67 ms	5012 KiB

knapsack

#include<bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


/*****************************************************************   Template Start  **************************************************************************/

#define endl                                    "\n"
#define int                                     long long
#define all(a)                                  a.begin(), a.end()
// #define sort(a)                                 sort(a.begin(), a.end())
#define sortrev(a)                              sort(a.rbegin(), a.rend())
#define prdouble(x)                             cout << fixed << setprecision(10) << x  

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>             ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>       ordered_multiset;
typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update>          ordered_greater_set;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update>    ordered_greater_multiset;
// find_by_order()
// order_of_key()

const int INF = 0x3f3f3f3f; // 1061109567
const int M = 1e9 + 7;
const int mod =  998244353;

void print(vector<int> v) { for(int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl;}

vector<int> input(int n) { vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; return a; }

vector<int> prime_factors(int n) { vector<int> prime; for(int i = 2; i*i <= n; i++) { while(n % i == 0) { prime.push_back(i);  n /= i; } } if(n > 1) { prime.push_back(n); } return prime; }

vector<int> divisors(int n) { vector<int> v; for(int i = 1; i*i <= n; i++) { if(n % i == 0) { v.push_back(i); if(i != n / i) { v.push_back(n / i); } } } return v; }

int gcd(int a, int b) { if(b == 0) { return a; } return gcd(b, a % b); }

int lcm(int a, int b) { return (a * b) / gcd(a, b); }

long long binMultiply(long long a, long long b, long long p) { long long ans = 0; a %= p; while(b > 0) { if(b & 1) { ans = (ans + a) % p; } a = (a + a) % p; b = b >> 1; } return ans; }

int binExp(int a, int b, int p) 
{
    if(b == 0) return 1;
    a %= p;
    if(b & 1) return (a * binExp(a, b - 1, p)) % p;
    else return binExp((a * a) % p, b >> 1, p);
}

class DSU{
    public:
    vector<int> par, rank, size;
    int n;
    DSU(int sz)
    {
        n = sz;
        rank.resize(n + 1, 0);
        size.resize(n + 1);
        par.resize(n + 1);
        for(int i = 0; i <= n; i++)
        {
            par[i] = i; 
            size[i] = 1; 
        }
    }

    int find(int node)
    {
        if(node == par[node])  return node;
        return par[node] = find(par[node]);
    }

    void merge(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v)  return; 
        if(size[u] < size[v])
        {
            par[u] = v;
            size[v] += size[u];
        }
        else
        {
            par[v] = u;
            size[u] += size[v];
        }
    }

    void mergeByRank(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v)  return; 
        if(rank[u] < rank[v]) par[u] = v;
        else if(rank[v] < rank[u]) par[v] = u; 
        else
        {
            par[v] = u;
            rank[u] += 1;
        }
    }
};

/*****************************************************************   Template End  **************************************************************************/


void solve() 
{
    int s, n;
    cin >> s >> n;
    priority_queue<pair<int, int>> pq[s + 1];
    for(int i = 0; i < n; i++)
    {
        int w, v, k;
        cin >> v >> w >> k;
        pq[w].push({v, k});
    }
    vector<int> dp(s + 1);

    for(int w = 1; w <= s; w++)
    {
        int cnt = s / w;
        while(!pq[w].empty() && cnt)
        {
            pair<int, int> p = pq[w].top();
            pq[w].pop();

            int value = p.first;
            int freq = p.second;

            freq = min(freq, cnt);
            cnt -= freq;

            for(int k = 1; k <= freq; k++)
            {
                for(int wt = s; wt >= w; wt--)
                {
                    dp[wt] = max(dp[wt], dp[wt - w] + value);
                }
            }
        }
    }
    int ans = 0;
    for(int w = 1; w <= s; w++) ans = max(ans, dp[w]);
    cout << ans << endl;

}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    clock_t z = clock();


    int t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }

    cerr << "Runtime : " << ((double)(clock() - z) / CLOCKS_PER_SEC) << endl;

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void print(std::vector<long long int>)':
knapsack.cpp:30:46: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | void print(vector<int> v) { for(int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl;}
      |                                            ~~^~~~~~~~~~

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