Submission #1112747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112747		ljtunas	Knapsack (NOI18_knapsack)	C++17	100 / 100	87 ms	47432 KiB

knapsack

// author : _anhtun.hi_
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define c_bit(i)       __builtin_popcountll(i)
#define Bit(mask, i)    ((mask >> i) & 1)
#define onbit(mask, i)  ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
#define all(data)      data.begin(), data.end()
#define reset(h, v)   memset(h, v, sizeof h)
#define Forv(i, a)    for(auto& i : a)
#define For(i, a, b)  for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
using namespace std;

void maximize(auto &a, auto b) {a = max(a, b);}
void minimize(auto &a, auto b) {a = min(a, b);}

#define int long long

const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0};
const int MAXN = 2e3  + 100, LOG = 20, base = 311;
const  ll  mod = 1e9  + 7;
const  ll   oo = 1e18;

int n, s;
vector<ii> List[MAXN];
ll a[MAXN][MAXN], dp[MAXN][MAXN];

void Solve(){
	cin >> s >> n;
	For(i, 1, n){
		int v, w, k;
		cin >> v >> w >> k;
		List[w].push_back({v, k});
	}
	reset(dp, 0); dp[0][0] = 0;
	For(w, 1, s){
		sort(all(List[w]), [&](ii a, ii b){
			return (a.fi > b.fi) || (a.fi == b.fi && a.se > b.se);
		});
		// For(S, 0, s) maximize(dp[w][S], dp[w - 1][S]);
		// if (List[w].size()) {
		int id = 0;
		for(auto [v, k] : List[w]){
			For(j, 1, k) {
				a[w][++id] = v;
				if (id > s / w) break; 
			}
			if (id > s / w) break; 
		}
		For(S, 0, s) {
			ll sum = 0;
			For(j, 0, id) if(S - w * j >= 0) {
				sum += a[w][j];
				maximize(dp[w][S], dp[w - 1][S - w * j] + sum);
			}
		}
		// }
	}
	cout << dp[s][s] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    if (fopen("NOI18_knapsack.inp", "r")){
        freopen("NOI18_knapsack.inp", "r", stdin);
        freopen("NOI18_knapsack.out", "w", stdout);
    }

    int tc = 1; // cin >> tc;
    while (tc --) Solve();
    return 0;
}

Compilation message (stderr)

knapsack.cpp:18:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maximize(auto &a, auto b) {a = max(a, b);}
      |               ^~~~
knapsack.cpp:18:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maximize(auto &a, auto b) {a = max(a, b);}
      |                        ^~~~
knapsack.cpp:19:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minimize(auto &a, auto b) {a = min(a, b);}
      |               ^~~~
knapsack.cpp:19:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minimize(auto &a, auto b) {a = min(a, b);}
      |                        ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen("NOI18_knapsack.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("NOI18_knapsack.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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