Submission #992967

#	Time	Username	Problem	Language	Result	Execution time	Memory
992967		cpdreamer	Knapsack (NOI18_knapsack)	C++17	73 / 100	1090 ms	2904 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <utility>
using namespace __gnu_pbds;
using namespace std;

typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;
const int max_n=INT_MAX;
typedef long long  ll;
#define LLM LONG_LONG_MAX
#define pb push_back
#define F first
#define L length()
#define all(v) v.begin(),v.end()
#define  P pair
#define V vector
#define S second
const long long MOD = 1000000007; // 1e9 + 7

void file(){
    freopen("input.txt.txt","r",stdin);
    freopen("output.txt.txt","w",stdout);
}
void setio(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
bool is_sorted(int A[],int n){
    for(int i=0;i<n-1;i++){
        if(A[i]>A[i+1])
            return false;
    }
    return true;
}
void solve() {
    int n,W;
    cin>>W>>n;
    int k[n],w[n],v[n];
    ll dp[W+1];
    bool made[W+1];
    memset(dp,-1,sizeof(dp));
    memset(made,0,sizeof(made));
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i]>>k[i];
    }
    dp[0]=0;
    made[0]=true;
    for(int i=0;i<n;i++){
        for(int j=W;j>=w[i];j--){
            for(int g=1;g<=k[i];g++){
                if(g*w[i]>j)
                    break;
                if(made[j-g*w[i]]){
                    dp[j]=max(dp[j],dp[j-g*w[i]]+v[i]*g);
                    made[j]=true;
                }

            }
        }
    }
    cout<<*max_element(dp,dp+W+1)<<endl;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //file();
    solve();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void file()':
knapsack.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen("input.txt.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen("output.txt.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void setio(std::string)':
knapsack.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     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: 0 / 27