답안 #860269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860269	2023-10-12T12:10:02 Z	Darren_Yang	Knapsack (NOI18_knapsack)	C++14	49 / 100	1000 ms	464 KB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define str string

// pairs
#define pi pair<int, int>
#define pl pair<ll, ll>
#define pd pair<ld, ld>
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rs resize
#define is insert
#define pb push_back
#define eb emplace_back
#define fr front()
#define bk back()

#define lb lower_bound
#define ub upper_bound

// loops
#define FOR(n) for(int i=0; i<(n); ++i)
#define FOR1(a, b) for(int i=(a); i<(b); ++i)
#define each(x, a) for(auto& x : a)

const int S=2e3;
ll s, n, v, w, k, dp[S+1];

void solve() {
    cin >> s >> n;
    if(n==1) {
        cin >> v >> w >> k;
        cout << v*min(s/w, k) << "\n";
    } else {
        FOR(n) {
            cin >> v >> w >> k;
            for(int j=0; j<k; ++j)
                for(int l=s; l-w>=0; --l)
                    dp[l]=max(dp[l-w]+v, dp[l]);
        }
        cout << dp[s] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

Subtask #1

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	456 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	464 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct

Subtask #4

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	456 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	2 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	464 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	146 ms	456 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Execution timed out	1051 ms	344 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	456 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	2 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	464 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	146 ms	456 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Execution timed out	1051 ms	344 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-