oj.uz

Submission #1112747

# Submission time Handle Problem Language Result Execution time Memory
1112747 2024-11-14T18:24:56 Z ljtunas Knapsack (NOI18_knapsack) C++17
100 / 100
 87 ms 47432 KB 
// 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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35408 KB Output is correct
2 Correct 6 ms 35588 KB Output is correct
3 Correct 7 ms 35408 KB Output is correct
4 Correct 8 ms 35408 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 34896 KB Output is correct
2 Correct 10 ms 35408 KB Output is correct
3 Correct 12 ms 34896 KB Output is correct
4 Correct 12 ms 34896 KB Output is correct
5 Correct 14 ms 34896 KB Output is correct
6 Correct 17 ms 35408 KB Output is correct
7 Correct 18 ms 35336 KB Output is correct
8 Correct 19 ms 35408 KB Output is correct
9 Correct 19 ms 35316 KB Output is correct
10 Correct 14 ms 35408 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 34896 KB Output is correct
2 Correct 10 ms 35408 KB Output is correct
3 Correct 12 ms 34896 KB Output is correct
4 Correct 12 ms 34896 KB Output is correct
5 Correct 14 ms 34896 KB Output is correct
6 Correct 17 ms 35408 KB Output is correct
7 Correct 18 ms 35336 KB Output is correct
8 Correct 19 ms 35408 KB Output is correct
9 Correct 19 ms 35316 KB Output is correct
10 Correct 14 ms 35408 KB Output is correct
11 Correct 8 ms 34896 KB Output is correct
12 Correct 17 ms 34896 KB Output is correct
13 Correct 17 ms 34908 KB Output is correct
14 Correct 18 ms 34896 KB Output is correct
15 Correct 15 ms 34896 KB Output is correct
16 Correct 23 ms 35368 KB Output is correct
17 Correct 16 ms 35408 KB Output is correct
18 Correct 19 ms 35408 KB Output is correct
19 Correct 18 ms 35264 KB Output is correct
20 Correct 23 ms 35372 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35408 KB Output is correct
2 Correct 6 ms 35588 KB Output is correct
3 Correct 7 ms 35408 KB Output is correct
4 Correct 8 ms 35408 KB Output is correct
5 Correct 7 ms 34896 KB Output is correct
6 Correct 10 ms 35408 KB Output is correct
7 Correct 12 ms 34896 KB Output is correct
8 Correct 12 ms 34896 KB Output is correct
9 Correct 14 ms 34896 KB Output is correct
10 Correct 17 ms 35408 KB Output is correct
11 Correct 18 ms 35336 KB Output is correct
12 Correct 19 ms 35408 KB Output is correct
13 Correct 19 ms 35316 KB Output is correct
14 Correct 14 ms 35408 KB Output is correct
15 Correct 8 ms 34896 KB Output is correct
16 Correct 17 ms 34896 KB Output is correct
17 Correct 17 ms 34908 KB Output is correct
18 Correct 18 ms 34896 KB Output is correct
19 Correct 15 ms 34896 KB Output is correct
20 Correct 23 ms 35368 KB Output is correct
21 Correct 16 ms 35408 KB Output is correct
22 Correct 19 ms 35408 KB Output is correct
23 Correct 18 ms 35264 KB Output is correct
24 Correct 23 ms 35372 KB Output is correct
25 Correct 17 ms 34896 KB Output is correct
26 Correct 21 ms 34896 KB Output is correct
27 Correct 15 ms 35064 KB Output is correct
28 Correct 12 ms 34896 KB Output is correct
29 Correct 11 ms 35612 KB Output is correct
30 Correct 16 ms 35408 KB Output is correct
31 Correct 12 ms 36088 KB Output is correct
32 Correct 14 ms 35408 KB Output is correct
33 Correct 13 ms 35408 KB Output is correct
34 Correct 14 ms 35408 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35408 KB Output is correct
2 Correct 6 ms 35588 KB Output is correct
3 Correct 7 ms 35408 KB Output is correct
4 Correct 8 ms 35408 KB Output is correct
5 Correct 7 ms 34896 KB Output is correct
6 Correct 10 ms 35408 KB Output is correct
7 Correct 12 ms 34896 KB Output is correct
8 Correct 12 ms 34896 KB Output is correct
9 Correct 14 ms 34896 KB Output is correct
10 Correct 17 ms 35408 KB Output is correct
11 Correct 18 ms 35336 KB Output is correct
12 Correct 19 ms 35408 KB Output is correct
13 Correct 19 ms 35316 KB Output is correct
14 Correct 14 ms 35408 KB Output is correct
15 Correct 8 ms 34896 KB Output is correct
16 Correct 17 ms 34896 KB Output is correct
17 Correct 17 ms 34908 KB Output is correct
18 Correct 18 ms 34896 KB Output is correct
19 Correct 15 ms 34896 KB Output is correct
20 Correct 23 ms 35368 KB Output is correct
21 Correct 16 ms 35408 KB Output is correct
22 Correct 19 ms 35408 KB Output is correct
23 Correct 18 ms 35264 KB Output is correct
24 Correct 23 ms 35372 KB Output is correct
25 Correct 17 ms 34896 KB Output is correct
26 Correct 21 ms 34896 KB Output is correct
27 Correct 15 ms 35064 KB Output is correct
28 Correct 12 ms 34896 KB Output is correct
29 Correct 11 ms 35612 KB Output is correct
30 Correct 16 ms 35408 KB Output is correct
31 Correct 12 ms 36088 KB Output is correct
32 Correct 14 ms 35408 KB Output is correct
33 Correct 13 ms 35408 KB Output is correct
34 Correct 14 ms 35408 KB Output is correct
35 Correct 39 ms 38264 KB Output is correct
36 Correct 45 ms 38592 KB Output is correct
37 Correct 43 ms 38336 KB Output is correct
38 Correct 35 ms 38312 KB Output is correct
39 Correct 41 ms 38916 KB Output is correct
40 Correct 79 ms 47432 KB Output is correct
41 Correct 69 ms 46664 KB Output is correct
42 Correct 66 ms 46664 KB Output is correct
43 Correct 87 ms 46596 KB Output is correct
44 Correct 74 ms 46664 KB Output is correct
45 Correct 47 ms 40184 KB Output is correct
46 Correct 39 ms 39112 KB Output is correct
47 Correct 46 ms 41288 KB Output is correct
48 Correct 61 ms 45468 KB Output is correct
49 Correct 38 ms 39248 KB Output is correct
50 Correct 54 ms 41288 KB Output is correct