Submission #526859

#	Time	Username	Problem	Language	Result	Execution time	Memory
526859		elesis	Knapsack (NOI18_knapsack)	C++14	12 / 100	1 ms	332 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define int long long 
#define pii pair<int,int> 
#define ff first
#define ss second
const int inf=1e9+7;
const int S=2007;
const int F=2;
//dp[i][j] represents the maximum value which can be obtained after choosing i objects with a total weight of j.
void solve()
{
    int N,W;
    cin>>W>>N;
    map<int,vector<pii>> mp;
    vector <vector <int>> dp(N+1,vector <int> (W+1,-inf));
    for(int i=0;i<N;i++)
    {
        int curw,curv,curk;
        cin>>curv>>curw>>curk;
        if(curw<=W && curk>0)
        mp[curw].push_back({curv,curk});
    }
    dp[0][0]=0; //base case
    int it=1; //the number of items being traversed.
    for(auto i:mp)
    {
        int w=i.first;
        vector <pii> arr=i.second;
        sort(arr.begin(),arr.end(),greater <pii> ());
        for(int j=0;j<=W;j++)
        {
            dp[it][j]=dp[it-1][j];
            int val=0,k1=0,cur=0,used=0;
            while((k1+1)*w<=j && cur<arr.size())
            {
                k1++;
                val+=arr[cur].first;
                if(dp[it-1][j-(k1*w)]!=-inf)
                {
                    dp[it][j]=max(dp[it][j],(dp[it-1][j-(k1*w)]+val));
                    //cout << dp[it][j] << " ";
                }
                used++;
                if(used==arr[cur].second)
                {
                    used=0;
                    cur++;
                }
            }
        }
        it++;
    }
    int ans=*max_element(dp.back().begin(),dp.back().end());
    cout << ans << '\n';
} 
signed main()
{
    fast
    clock_t start, end;
    start = clock();
    solve();
    end = clock();
    double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
    //cout << "time taken" << " " << time_taken << "\n";
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:36:37: 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]
   36 |             while((k1+1)*w<=j && cur<arr.size())
      |                                  ~~~^~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:65:12: warning: unused variable 'time_taken' [-Wunused-variable]
   65 |     double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
      |            ^~~~~~~~~~

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