Submission #986989

#	Time	Username	Problem	Language	Result	Execution time	Memory
986989		Codurr	Knapsack (NOI18_knapsack)	C++14	100 / 100	65 ms	9932 KiB

knapsack

#include "bits/stdc++.h"
using namespace std;

#define int long long //Avoid if time complexity very close to limit
#define ll long long
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define f first
#define s second

void setIO(string s="") {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(sz(s)) {
        freopen((s+".in").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

//Imp consts
const int MOD=1e9+7;
const int MAXN=2e5+1;
const int INF=1e18+5;
const double pi=3.14159265358979323846;
const double ep=1e-20;

signed main() {
    setIO();
    int S,n;
    cin>>S>>n;
    vector<int> val,wt,cnt;  
    map<int,vector<pair<int, int>>> m;
    for(int i=0;i<n;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        m[y].push_back({x,z});
        val.push_back(x);
        wt.push_back(y);
        cnt.push_back(z);
    }
    vector<int> dp(S+1,-1);
    dp[0]=0;
    if(n==1) {
        int ans=min(cnt[0],(S/wt[0]))*val[0];
        cout<<ans;
        return 0;
    }
    for(auto u:m) {
        int wt=u.f,val=u.s[0].f,cnt=0,i=0;
        
        vector<pair<int, int>> v=u.s;
        sort(rall(v));
        vector<int> z;
        int cur=0;
        while(i<sz(v)&&sz(z)<=S/wt) {
            int cur=0;
            while(cur<v[i].s&&sz(z)<=S/wt) {
                z.push_back(v[i].f);
                cur++;
            }
            i++;
        }
        for(auto xx:z) {
            for(int j=S;j>=wt;j--) {
                dp[j]=max(dp[j],dp[j-wt]+xx);
            }
        }
    }
    int ans=0;
    for(auto u:dp)
        ans=max(ans,u);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:49:20: warning: unused variable 'val' [-Wunused-variable]
   49 |         int wt=u.f,val=u.s[0].f,cnt=0,i=0;
      |                    ^~~
knapsack.cpp:49:33: warning: unused variable 'cnt' [-Wunused-variable]
   49 |         int wt=u.f,val=u.s[0].f,cnt=0,i=0;
      |                                 ^~~
knapsack.cpp:54:13: warning: unused variable 'cur' [-Wunused-variable]
   54 |         int cur=0;
      |             ^~~
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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