Submission #765842

#	Time	Username	Problem	Language	Result	Execution time	Memory
765842		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	52 ms	3872 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
long long n,m,k,p=1e9+7;
long long power(long long a,long long b){
                if(b==0)return 1;
                long long ans=power(a,b/2);
                ans*=ans;
                ans%=p;
                if(b%2)ans*=a;
                ans%=p;
                return ans;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
                                        int T=1;
                                        // cin>>T;
                                        while(T--){
                                                cin>>m>>n;
                                                vector<vector<pair<int,int>>>a(m+1);
                                                for(int i=0;i<n;i++){
                                                        int v,w,k;
                                                    cin>>v>>w>>k;
                                                    a[w].push_back({v,k});
                                                }
                                                for(int i=1;i<=m;i++){
                                                    sort(a[i].begin(),a[i].end());
                                                    reverse(a[i].begin(),a[i].end());
                                                }
                                                long long ans=0;
                                                vector<long long>b,c;
                                                for(int i=m;i>=1;i--){
                                                    int cnt=m/i;
                                                    for(auto j:a[i]){
                                                        while(j.second>0 && cnt>0){
                                                            cnt--;
                                                            j.second--;
                                                            b.push_back(j.first);
                                                            c.push_back(i);
                                                        }
                                                        if(cnt==0)break;
                                                    }
                                                }
                                                vector<long long>dp(m+1,-1);
                                                dp[0]=0;
                                                for(int i=0;i<c.size();i++){
                                                    for(int j=m-c[i];j>=0;j--){
                                                        if(dp[j]!=-1){
                                                            dp[j+c[i]]=max(dp[j+c[i]],dp[j]+b[i]);
                                                        }
                                                    }
                                                }
                                                for(int i=1;i<=m;i++)ans=max(ans,dp[i]);
                                                cout<<ans<<'\n';
                                    }
                    return 0;
         }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:45:62: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                                                 for(int i=0;i<c.size();i++){
      |                                                             ~^~~~~~~~~

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