Submission #688610

#	Time	Username	Problem	Language	Result	Execution time	Memory
688610		koolaider	Knapsack (NOI18_knapsack)	C++17	73 / 100	796 ms	262144 KiB

knapsack

    #include <bits/stdc++.h>
    #include <cstdlib>
    using namespace std;
     
    void setIO(string s) {
    	freopen((s + ".in").c_str(), "r", stdin);
    	freopen((s + ".out").c_str(), "w", stdout);
    }
     
     
    #define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl
    #define pb push_back
    #define ll long long
     
    const int MN = 1e5+2;
     
    void __print(int x) {cerr << x;}
    void __print(long x) {cerr << x;}
    void __print(long long x) {cerr << x;}
    void __print(unsigned x) {cerr << x;}
    void __print(unsigned long x) {cerr << x;}
    void __print(unsigned long long x) {cerr << x;}
    void __print(float x) {cerr << x;}
    void __print(double x) {cerr << x;}
    void __print(long double x) {cerr << x;}
    void __print(char x) {cerr << '\'' << x << '\'';}
    void __print(const char *x) {cerr << '\"' << x << '\"';}
    void __print(const string &x) {cerr << '\"' << x << '\"';}
    void __print(bool x) {cerr << (x ? "true" : "false");}
     
    template<typename T, typename V>
    void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
    template<typename T>
    void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
    void _print() {cerr << "]\n";}
    template <typename T, typename... V>
    void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
    #ifndef ONLINE_JUDGE
    #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
    #else
    #define debug(x...)
    #endif
     
    /*
      a b y x b
    a 1 1 1 1 1
    x 1 1 1 2 2
    y 1 1 2 2 2
    b 1 2 2 2 3
     */
     
    #pragma GCC target ("avx,avx2")
    #pragma GCC optimize ("Ofast")
    //DSUFlowHyRuthTh!
     
     
    //const long long ML = 1e18;
    //const int MN = 1e9;
     
    const int MM = 1e9+7;
     
     
    int main(int argc, char **argv){
    	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);	
    	//setIO("time");
    	ll s, n; cin >> s >> n;
    	ll v, w, k; 
    	// dp[i][j]=max number of items we can pick considering the weight
    	vector<ll> values; values.reserve(1e9); 
    	vector<ll> weights; weights.reserve(1e9); 
    	for(ll i = 0; i<n; i++){
    		cin >> v >> w >> k;
    		for(ll j = 0; j<min(k, s/w); j++){
    			values.pb(v); weights.pb(w);
    			//values.pb(v*k-1); weights.pb(w*k-1);
    			}
    	}
    	ll amount = values.size();
    	ll dp[2][s+1]; memset(dp, 0, sizeof(dp));
    	bool f = true;
    	for(ll y = 1; y<=amount; y++){
    		for(ll x = 1; x<=s; x++){
    		if(f==true){
    		if(x-weights[y-1]>=0) dp[0][x]=dp[1][x-weights[y-1]]+values[y-1];
    		dp[0][x]=max(dp[0][x], dp[1][x]);
    		}else{
    		if(x-weights[y-1]>=0) dp[1][x]=dp[0][x-weights[y-1]]+values[y-1];
    		dp[1][x]=max(dp[1][x], dp[0][x]);	
    		}
    		}
    	/*
    	for(int x = 1; x<=s; x++){
    		if(f==true){
    		dp[2][x]=dp[1][x];
    		}else{
    		dp[0][x]=dp[2][x];
    		}
    		}
    	*/
    	f=!f;
    	}
    	cout << max(dp[0][s], dp[1][s]);
    	return 0;
    }

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:6:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |      freopen((s + ".in").c_str(), "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:7:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |      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