Submission #1112742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112742		ljtunas	Knapsack (NOI18_knapsack)	C++17	0 / 100	193 ms	262144 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  + 10, LOG = 20, base = 311;
const  ll  mod = 1e9  + 7;
const  ll   oo = 1e18;

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

ll solve(int i, int S, int j){
	if (S < 0) return -oo;
	if (i > s) return (S == 0) ? 0 : -oo;
	if (~dp[i][S][j]) return dp[i][S][j];
	ll res = 0;
	maximize(res, solve(i + 1, S, 0));
	if (a[i][j + 1] != 0)
	maximize(res, solve(i, S - i, j + 1) + a[i][j + 1]);
	return dp[i][S][j] = res;
}

void Solve(){
	cin >> s >> n;
	For(i, 1, n){
		int v, w, k;
		cin >> v >> w >> k;
		List[w].push_back({v, k});
	}
	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);
		});
		if (List[w].size()) {
			int id = 0;
			// cerr << w << '\n';
			for(auto [v, k] : List[w]){
				// cerr << v << ' ' << k << '\n';
				For(j, 1, k) {
					a[w][++id] = v;
					if (id > s / w + 10) break; 
				}
				if (id > s / w + 10) break; 
			}
			idx[w] = id;
			// For(j, 1, id) cerr << a[w][j] << ' '; cerr << '\n';
		}
		dp[w].assign(s + 2, vector<ll>(s / w + 20, -1));
	}
	cout << solve(1, s, 0) << '\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:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("NOI18_knapsack.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen("NOI18_knapsack.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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