Submission #912704

#	Time	Username	Problem	Language	Result	Execution time	Memory
912704		Taresu	Knapsack (NOI18_knapsack)	C++11	100 / 100	72 ms	5212 KiB

knapsack

    #include <bits/stdc++.h>
     
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
         
    #define INF 0x7fffffff
    #define MINF -0x7fffffff
    #define pb push_back
    #define sz(a) a.size()
    #define mod 998244353
    #define MOD 1000000007
    #define f first
    #define s second   
    #define sortv(a) sort(a.begin(), a.end())
    #define rsortv(a) sort(a.rbegin(), a.rend())
    #define ins insert
    #define fr(i, a) for(int i=0;i<a;i++)
    #define mem0(a) memset(a, 0, sizeof(a))
    #define mem1(a) memset(a, 1, sizeof(a))
    #define mem_1(a) memset(a, -1, sizeof(a))
    #define memI(a) memset(a, INF, sizeof(a))
    #define formap(it, a) for(map<int, int>::iterator it=a.begin();it!=a.end();it++)
    #define forset(it, a) for(unordered_set<int>::iterator it=a.begin();it!=a.end();it++)
    #define formset(it, a) for(multiset<int>::iterator it=a.begin();it!=a.end();it++)

    using namespace std;   
    using namespace __gnu_pbds;
     
    typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
     
    typedef long long int ll;
    typedef pair<ll, ll> pii;
    typedef pair<int, pair<int, int> > pipii;
    typedef priority_queue<pii> pqueue;
 
 
    ll gcd(ll a, ll b){
        return b==0 ? a : gcd(b, a%b); 
    }
    ll lcm(ll a, ll b){
        return (a*b)/gcd(a, b); 
    }
    ll fexp(ll b, ll e, ll m){
        if(e==0) return 1;
        if(e==1) return b%m;
 
        ll h=fexp(b, e/2, m);
        if(e%2==0){
            return (h*h)%m;
        }else{
            return (((h*h)%m)*b)%m;
        }
    }
    ll inv(ll x, ll m){
	    if (x <= 1) {
             return x;
        }
	    return m-m/x*inv(m % x, m)%m;
    }
    void irr(ll *a, ll *b){ //deixar primos entre si
        ll gc=gcd(*a, *b);
        *a/=gc;
        *b/=gc;
    }
    ll divmod(ll num, ll den, ll m){
        return (num*fexp(den, m-2, m))%m;
    }
    void read(vector<int> &V){
        int a;
        cin >> a;
        V.pb(a);
    }
 
    ///////////////SOLVE
    //////////////////////////////////
    ///////////////////////

    ll dp[2][2020];
    pqueue weight[2002];
    vector<int> w;
    vector<int> v;

    void solve(){
        mem0(dp);

        int S, n;
        cin >> S >> n;

        fr(i, n){
            int a, b, c;
            cin >> a >> b >> c;
            weight[b].push({a, c});
        }
        
        fr(i, S){
            int j=0;
            while(j<=S/(i+1) && !weight[i+1].empty()){
                int times=weight[i+1].top().s;
                int val=weight[i+1].top().f;
                weight[i+1].pop();
                while(j<=S/(i+1) && times){
                    w.pb(i+1);
                    v.pb(val);
                    j++;
                    times--;
                }
            }
        }

        fr(i, sz(w)){
            int at=(i+1)%2;
            int ls=!at;
            fr(j, S+1){
               dp[at][j]=max(dp[ls][j], dp[at][j]);
               if(j-w[i]>=0){
                dp[at][j]=max(dp[at][j], dp[ls][j-w[i]]+v[i]);
               }
            }
        }

        cout << dp[sz(w)%2][S] << '\n';
    }

    ///////////////SOLVE
    //////////////////////////////////
    ////////////////////////
 
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        /*/freopen("cbarn2.in","r",stdin);
	    freopen("cbarn2.out","w",stdout);/**/
        int t=1;
        //cin >> t;
        
        while(t--){
            solve();
        }
 
        return 0;
    }

Compilation message (stderr)

knapsack.cpp:132:39: warning: "/*" within comment [-Wcomment]
  132 |      freopen("cbarn2.out","w",stdout);/**/
      |                                        
knapsack.cpp: In function 'void solve()':
knapsack.cpp:17:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     #define fr(i, a) for(int i=0;i<a;i++)
      |                                   ^
knapsack.cpp:110:9: note: in expansion of macro 'fr'
  110 |         fr(i, sz(w)){
      |         ^~

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