Submission #783854

#	Time	Username	Problem	Language	Result	Execution time	Memory
783854		tr1ten	Knapsack (NOI18_knapsack)	C++17	100 / 100	88 ms	34232 KiB

knapsack

    #include <cstdio>
    #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;
    template<class T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
    template<typename T> 
    using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
    // find_by_order(k)  returns iterator to kth element starting from 0;
    // order_of_key(k) returns count of elements strictly smaller than k;
    // useful defs
    typedef long long ll; 
    typedef vector<ll> vi;
    typedef vector<vi> vii;
    typedef pair<ll,ll> pi;
    typedef vector<pi> vpi;
    typedef unordered_map<ll,ll> mll;
    #define pb push_back
    #define mp make_pair
    #define rep(i,a,b) for (int i = (a); i < (b); i++)
    #define per(i,a,b) for (int i = (b)-1; i >= (a); i--)
    #define trav(a,arr) for (auto& a: (arr))
    #define sz(x) (int)(x).size()
    #define mk_vec(name,sz,value) vi name(sz,value)
    #define mk_mat(name,n,m,value) vii name(n, vi(m, value))
    #define contains(x) find(x) != string::npos
    #define tkv(vec,sz) rep(i,0,sz) cin>>vec[i]
    #define srv(vec) sort(vec.begin(), vec.end())
    #define all(x) x.begin(), x.end()
    #define less(a,b) a<b
    #define vsum(vec) accumulate(vec.begin(), vec.end(), 0L);
    #define vmax(vec) *max_element(vec.begin(), vec.end());
    #define vmin(vec) *min_element(vec.begin(), vec.end());
    #define pvc(vec) trav(x,vec) cout<<x<<" "; cout<<endl;
    #define put(x) cout<<(x)<<endl;
    #define put2(x,y) cout<<(x)<<" "<<(y)<<endl;
    #define put3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl;
    #define mod(x) (x + MOD)%MOD
    // debugging
    #define timed(x) {auto start = chrono::steady_clock::now(); x; auto end = chrono::steady_clock::now(); auto diff = end - start; cout << chrono::duration <double, milli> (diff).count() << " ms" << endl;}
     
     
    void __print(int x) {cerr << x;}
    void __print(long x) {cerr << x;}
    void __print(long long x) {cerr << x;}
    void __print(unsigned x) {cerr << x;}
    void __print(unsigned long x) {cerr << x;}
    void __print(unsigned long long x) {cerr << x;}
    void __print(float x) {cerr << x;}
    void __print(double x) {cerr << x;}
    void __print(long double x) {cerr << x;}
    void __print(char x) {cerr << '\'' << x << '\'';}
    void __print(const char *x) {cerr << '\"' << x << '\"';}
    void __print(const string &x) {cerr << '\"' << x << '\"';}
    void __print(bool x) {cerr << (x ? "true" : "false");}
     
    template<typename T, typename V>
    void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
    template<typename T>
    void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
    void _print() {cerr << "]\n";}
    template <typename T, typename... V>
    void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
     
    #ifndef ONLINE_JUDGE
    #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
    #else
    #define debug(x...)
    #endif
    const ll MOD = 1e9+7;
    const ll INF = 1e10+5;
     
    // driver code
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        // freopen("input.in","r",stdin);
        // freopen("output.out","w",stdout);	  
        int T=1;
        // cin>>T;
        while(T--){
            ll S,N;
            cin >> S >> N;
            map<ll,vpi> wts;
            rep(i,0,N){
                ll a,b,c;
                cin >> a >> b >> c;
                if(b<=S && c>0) wts[b].push_back({a,c});
            }
            ll dp[wts.size()+1][S+1]; 
            memset(dp,0,sizeof dp);
            ll at = 1;
            for(auto [wt,items]:wts){
                srv(items);
                reverse(all(items));
                rep(j,1,S+1){
                    dp[at][j] = dp[at-1][j];
                    int tid = 0;
                    int cur_used = 0;
                    ll copies = 0;
                    ll profit = 0;
                    while(tid<items.size() && (copies+1)*wt<=j ){
                        copies++;
                        profit += items[tid].first;
                        dp[at][j] = max(dp[at][j],profit + dp[at-1][j-wt*copies]);
                        cur_used++;
                        if(cur_used==items[tid].second){
                            cur_used = 0;
                            tid++;
                        }
                    }
                }
                at++;
            }
            put(dp[at-1][S]);
        }
     
        return 0;
    }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:106:30: 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]
  106 |                     while(tid<items.size() && (copies+1)*wt<=j ){
      |                           ~~~^~~~~~~~~~~~~

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