/*
o((>ω< ))o
o(≧口≦)o
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define int ll
#define F first
#define S second
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
//#define endl "\n"
struct mrbeast{
int v; int w; int k;
};
struct roblox{
int w; int v;
};
void solve(){
int S,n,m;
cin >> S >> n;
vector<mrbeast> a_(1e5+10);
vector<roblox> a(3000);
vector<vector<int>> dp(3000,vector<int>(2005));
for (int i = 1; i <= n; i++) cin >> a_[i].v >> a_[i].w >> a_[i].k;
m = 0;
for (int i = 1; i <= n; i++){
for (int j = 0; (1 << j) <= a_[i].k; j++){
a_[i].k -= (1 << j);
a[++m].w = a_[i].w*(1<<j);
a[m].v = a_[i].v*(1<<j);
}
if (a_[i].k > 0){
a[++m].w = a_[i].w*a_[i].k;
a[m].v = a_[i].v*a_[i].k;
}
}
/*
cout << endl;
for (int i = 1; i <= m; i++) cout << a[i].w << ' ' << a[i].v << endl;
*/
for (int i = 1; i <= m; i++){
for (int j = 0; j <= S; j++){
dp[i][j] = dp[i-1][j];
if (a[i].w <= j){
dp[i][j] = max(dp[i-1][j],dp[i-1][j-a[i].w]+a[i].v);
}
}
}
/*
cout << "-----------" << endl;
for (int i = 1; i <= m; i++){
for (int j = 0; j <= S; j++){
cout << dp[i][j] << ' ';
}
cout << endl;
}
cout << "-----------" << endl;
*/
cout << dp[m][S] << endl;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int t; cin >> t; while (t--)
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
50008 KB |
Output is correct |
2 |
Correct |
15 ms |
50040 KB |
Output is correct |
3 |
Correct |
15 ms |
49808 KB |
Output is correct |
4 |
Correct |
16 ms |
50012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
50008 KB |
Output is correct |
2 |
Correct |
23 ms |
49948 KB |
Output is correct |
3 |
Correct |
18 ms |
49820 KB |
Output is correct |
4 |
Correct |
19 ms |
50012 KB |
Output is correct |
5 |
Correct |
15 ms |
50012 KB |
Output is correct |
6 |
Correct |
15 ms |
49932 KB |
Output is correct |
7 |
Correct |
20 ms |
50008 KB |
Output is correct |
8 |
Correct |
21 ms |
49948 KB |
Output is correct |
9 |
Correct |
15 ms |
50012 KB |
Output is correct |
10 |
Correct |
15 ms |
50012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
50008 KB |
Output is correct |
2 |
Correct |
23 ms |
49948 KB |
Output is correct |
3 |
Correct |
18 ms |
49820 KB |
Output is correct |
4 |
Correct |
19 ms |
50012 KB |
Output is correct |
5 |
Correct |
15 ms |
50012 KB |
Output is correct |
6 |
Correct |
15 ms |
49932 KB |
Output is correct |
7 |
Correct |
20 ms |
50008 KB |
Output is correct |
8 |
Correct |
21 ms |
49948 KB |
Output is correct |
9 |
Correct |
15 ms |
50012 KB |
Output is correct |
10 |
Correct |
15 ms |
50012 KB |
Output is correct |
11 |
Correct |
21 ms |
49840 KB |
Output is correct |
12 |
Correct |
17 ms |
49920 KB |
Output is correct |
13 |
Correct |
16 ms |
50012 KB |
Output is correct |
14 |
Correct |
16 ms |
49860 KB |
Output is correct |
15 |
Correct |
17 ms |
50032 KB |
Output is correct |
16 |
Correct |
16 ms |
50012 KB |
Output is correct |
17 |
Correct |
16 ms |
49848 KB |
Output is correct |
18 |
Correct |
16 ms |
49904 KB |
Output is correct |
19 |
Correct |
18 ms |
49848 KB |
Output is correct |
20 |
Correct |
17 ms |
49856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
50008 KB |
Output is correct |
2 |
Correct |
15 ms |
50040 KB |
Output is correct |
3 |
Correct |
15 ms |
49808 KB |
Output is correct |
4 |
Correct |
16 ms |
50012 KB |
Output is correct |
5 |
Correct |
16 ms |
50008 KB |
Output is correct |
6 |
Correct |
23 ms |
49948 KB |
Output is correct |
7 |
Correct |
18 ms |
49820 KB |
Output is correct |
8 |
Correct |
19 ms |
50012 KB |
Output is correct |
9 |
Correct |
15 ms |
50012 KB |
Output is correct |
10 |
Correct |
15 ms |
49932 KB |
Output is correct |
11 |
Correct |
20 ms |
50008 KB |
Output is correct |
12 |
Correct |
21 ms |
49948 KB |
Output is correct |
13 |
Correct |
15 ms |
50012 KB |
Output is correct |
14 |
Correct |
15 ms |
50012 KB |
Output is correct |
15 |
Correct |
21 ms |
49840 KB |
Output is correct |
16 |
Correct |
17 ms |
49920 KB |
Output is correct |
17 |
Correct |
16 ms |
50012 KB |
Output is correct |
18 |
Correct |
16 ms |
49860 KB |
Output is correct |
19 |
Correct |
17 ms |
50032 KB |
Output is correct |
20 |
Correct |
16 ms |
50012 KB |
Output is correct |
21 |
Correct |
16 ms |
49848 KB |
Output is correct |
22 |
Correct |
16 ms |
49904 KB |
Output is correct |
23 |
Correct |
18 ms |
49848 KB |
Output is correct |
24 |
Correct |
17 ms |
49856 KB |
Output is correct |
25 |
Correct |
25 ms |
50004 KB |
Output is correct |
26 |
Correct |
27 ms |
50012 KB |
Output is correct |
27 |
Correct |
15 ms |
50012 KB |
Output is correct |
28 |
Correct |
16 ms |
50012 KB |
Output is correct |
29 |
Correct |
19 ms |
49908 KB |
Output is correct |
30 |
Correct |
19 ms |
50060 KB |
Output is correct |
31 |
Correct |
25 ms |
50012 KB |
Output is correct |
32 |
Correct |
18 ms |
50012 KB |
Output is correct |
33 |
Correct |
17 ms |
50008 KB |
Output is correct |
34 |
Correct |
17 ms |
49844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
50008 KB |
Output is correct |
2 |
Correct |
15 ms |
50040 KB |
Output is correct |
3 |
Correct |
15 ms |
49808 KB |
Output is correct |
4 |
Correct |
16 ms |
50012 KB |
Output is correct |
5 |
Correct |
16 ms |
50008 KB |
Output is correct |
6 |
Correct |
23 ms |
49948 KB |
Output is correct |
7 |
Correct |
18 ms |
49820 KB |
Output is correct |
8 |
Correct |
19 ms |
50012 KB |
Output is correct |
9 |
Correct |
15 ms |
50012 KB |
Output is correct |
10 |
Correct |
15 ms |
49932 KB |
Output is correct |
11 |
Correct |
20 ms |
50008 KB |
Output is correct |
12 |
Correct |
21 ms |
49948 KB |
Output is correct |
13 |
Correct |
15 ms |
50012 KB |
Output is correct |
14 |
Correct |
15 ms |
50012 KB |
Output is correct |
15 |
Correct |
21 ms |
49840 KB |
Output is correct |
16 |
Correct |
17 ms |
49920 KB |
Output is correct |
17 |
Correct |
16 ms |
50012 KB |
Output is correct |
18 |
Correct |
16 ms |
49860 KB |
Output is correct |
19 |
Correct |
17 ms |
50032 KB |
Output is correct |
20 |
Correct |
16 ms |
50012 KB |
Output is correct |
21 |
Correct |
16 ms |
49848 KB |
Output is correct |
22 |
Correct |
16 ms |
49904 KB |
Output is correct |
23 |
Correct |
18 ms |
49848 KB |
Output is correct |
24 |
Correct |
17 ms |
49856 KB |
Output is correct |
25 |
Correct |
25 ms |
50004 KB |
Output is correct |
26 |
Correct |
27 ms |
50012 KB |
Output is correct |
27 |
Correct |
15 ms |
50012 KB |
Output is correct |
28 |
Correct |
16 ms |
50012 KB |
Output is correct |
29 |
Correct |
19 ms |
49908 KB |
Output is correct |
30 |
Correct |
19 ms |
50060 KB |
Output is correct |
31 |
Correct |
25 ms |
50012 KB |
Output is correct |
32 |
Correct |
18 ms |
50012 KB |
Output is correct |
33 |
Correct |
17 ms |
50008 KB |
Output is correct |
34 |
Correct |
17 ms |
49844 KB |
Output is correct |
35 |
Runtime error |
66 ms |
102056 KB |
Execution killed with signal 11 |
36 |
Halted |
0 ms |
0 KB |
- |