Submission #428431

#	Time	Username	Problem	Language	Result	Execution time	Memory
428431		Karliver	Knapsack (NOI18_knapsack)	C++14	73 / 100	421 ms	262148 KiB

knapsack

	
 #include <bits/stdc++.h>
 
 #define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
 #define all(v) (v).begin(), (v).end()
 using namespace  std;
 #define forn(i,n) for (int i = 0; i < (n); ++i)
 #define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
 using ll = long long;
 int mod = (ll)1e9 + 7;
 #define PI acos(-1)
 typedef pair<int, int> pairs;
 
 const int INF = 1e9 + 1;
 const int N = 2e5 + 100;
 const double eps = 1e-7;
 
 template <class T> using V = vector<T>;  
 template <class T> using VV = V<V<T>>;  
 
 template <typename XPAX>
 void ckma(XPAX &x, XPAX y) {
     x = (x < y ? y : x);
 }
 template <typename XPAX>
 void ckmi(XPAX &x, XPAX y) {
     x = (x > y ? y : x);
 }
 
 void solve() {
 
 
 	int S, n;
 	cin >> S >> n;

 	V<int> val(n), w(n), k(n);
 	forn(i, n) {
 		cin >> val[i] >> w[i] >> k[i];
 	}

 	V<int> dp(S + 1, -1);
 	dp[0] = 0;
 	forn(i, n) {
 		int cantake = min(k[i], S / w[i]);
 		cantake--;
 		while(cantake-- > 0) {
 			val.push_back(val[i]);
 			w.push_back(w[i]);
 		}
 	}

 	forn(i, w.size()) {
 		for(int x = S;x > 0;--x) {
 			if(x - w[i] >= 0 && dp[x - w[i]] != -1)
 				ckma(dp[x], dp[x - w[i]] + val[i]);
 		}
 	}
 	cout << *max_element(all(dp)) << '\n';

 
 
 
 }
 void test_case() {
     int t;
     cin >> t;
     forn(p, t) {
 
         //cout << "Case #" << p + 1 << ": ";
         solve();
     }
 }
 int main() {
 
     ios::sync_with_stdio(false);
     cin.tie(0);
 
     solve();
 
 }
  

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:7:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |  #define forn(i,n) for (int i = 0; i < (n); ++i)
      |                                      ^
knapsack.cpp:52:3: note: in expansion of macro 'forn'
   52 |   forn(i, w.size()) {
      |   ^~~~

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