oj.uz

Submission #688623

# Submission time Handle Problem Language Result Execution time Memory
688623 2023-01-27T21:12:47 Z koolaider Knapsack (NOI18_knapsack) C++17
73 / 100
 307 ms 262144 KB 
    #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;
    	vector<ll> weights; 
    	for(ll i = 0; i<n; i++){
    		cin >> v >> w >> k;
    		if(w<=s){
    		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);
    			}
    		}
    	}
    	values.shrink_to_fit();
    	weights.shrink_to_fit();
    	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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 352 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 352 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 268 ms 2880 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 3 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 352 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 268 ms 2880 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 3 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 18 ms 2880 KB Output is correct
36 Runtime error 307 ms 262144 KB Execution killed with signal 9
37 Halted 0 ms 0 KB -