Submission #975818

#	Time	Username	Problem	Language	Result	Execution time	Memory
975818		Isam	Knapsack (NOI18_knapsack)	C++17	100 / 100	563 ms	5392 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
 
#define eb emplace_back
//#define int long long


inline int read() {
  //  opt = 0;
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    //if (ch == ' ') opt = 1;
    return x * f;
}

constexpr int sz = 1e5 + 5;
constexpr long long inf = (long long)1E18 + 7;

int n, s;

multiset<pair<int, int>> a[2005];

long long dp[2005];

signed main(){
	s = read(), n = read();
	for(register int i = 1, v, w, k; i <= n; ++i){
		v = read(), w = read(), k = read();
		k = min(k, s / w);
		a[w].insert({-v, -k});
	}
	
	for(register int i = 1; i <= 2000; ++i) dp[i] = -inf;
	
	for(register int i = 1; i <= s; ++i){
		
		int tot(0);
		
		for(auto it = a[i].begin(); it != a[i].end(); ++it){
			
			int k = it->second, v = it->first;
			k *= -1, v *= -1;
			
			if(tot > 2000) break;
			
			tot += k;
			
			while(k--){
				
				for(register int j = s; j >= i; --j) dp[j] = max(dp[j], dp[j - i] + v);
				
			}
			
		}
		
	}
	
	cout << *max_element(dp, dp+s+1) << '\n';
	
	
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:35:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   35 |  for(register int i = 1, v, w, k; i <= n; ++i){
      |                   ^
knapsack.cpp:35:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   35 |  for(register int i = 1, v, w, k; i <= n; ++i){
      |                          ^
knapsack.cpp:35:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   35 |  for(register int i = 1, v, w, k; i <= n; ++i){
      |                             ^
knapsack.cpp:35:32: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   35 |  for(register int i = 1, v, w, k; i <= n; ++i){
      |                                ^
knapsack.cpp:41:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   41 |  for(register int i = 1; i <= 2000; ++i) dp[i] = -inf;
      |                   ^
knapsack.cpp:43:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   43 |  for(register int i = 1; i <= s; ++i){
      |                   ^
knapsack.cpp:58:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   58 |     for(register int j = s; j >= i; --j) dp[j] = max(dp[j], dp[j - i] + v);
      |                      ^

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