oj.uz

Submission #1085046

# Submission time Handle Problem Language Result Execution time Memory
1085046 2024-09-07T11:58:37 Z NVTH Knapsack (NOI18_knapsack) C++14
73 / 100
 1000 ms 3928 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define file "test"
#define pb push_back
#define all(x) begin(x), end(x)
#define FOR( i, start, end, step ) for ( int i=start; i<=end; i += step )
#define FORD( i, start, end, step ) for ( int i=start; i>=end; i -= step )
using namespace std;

const ll N   = 1e5+1;
const ll NN  = 1e3+9;
const ld eps = 1e-7;
const ll oo  = 1e16 + 1;
const ll MOD = 1e9+7;

struct Item
    {
        ll v, w, k;
    } a[N];
ll S, n, dp[2002], res = 0;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
            // freopen(file".inp","r",stdin);
            // freopen(file".out","w",stdout);
    #endif
    cin >> S >> n;
    FOR ( i, 1, n, 1 )
        cin >> a[i].v >> a[i].w >> a[i].k;

    // cout << 0 ;
    // FOR ( i, 0, n, 1 )
    //     {
    //         FOR ( w, 0, S, 1 )
    //             {
    //                 int limit = min ( a[i].k, S / a[i].w );
    //                 if ( i == 0 || w == 0 ) dp[i][w] = 0;
    //                 else if ( a[i - 1].w <= w ) 
    //                     {
    //                         FOR ( k, 1, limit, 1 ) 
    //                             {
    //                                 dp[i][w] = max ( ( a[i-1].v * k ) + dp[i-1][w- ( a[i-1].w * k )], dp[i-1][w] );
    //                             }
    //                     }
    //                 else
    //                     dp[i][w] = dp[i - 1][w];
    //             }
    //     }

    FOR ( i, 1, n, 1 )
        FORD ( j, S, a[i].w, 1 )
            {
                int limit = min ( a[i].k, j / a[i].w );
                FOR ( z, 1, limit, 1 )
                    {
                        if ( j >= ( a[i].w * z ) ) 
                            {
                                if ( dp[j - ( a[i].w * z )] != -oo ) dp[j] = max ( dp[j - ( a[i].w * z )] + ( a[i].v * z ), dp[j] );
                            }
                    }
                res = max ( res, dp[j] );
            }

    cout << res;
    return 0;
}
/*

....____............._...__....................................._ ...__..........______ __....._.................__..__.............
.../ __ ).__  __..../ | / /____ _ __..__ __..__ ___...____.....| |../ /____...../_  __// /_...(_)___...____...../ / / /____ _ ____..
../ __  |/ / / /.../  |/ // __ `// / / // / / // _ \ / __ \....| | / // __ \...../ /../ __ \./ // _ \ / __ \.../ /_/ // __ `// __ \.
./ /_/ // /_/ /.../ /|  // /_/ // /_/ // /_/ //  __// / / /....| |/ // /_/ /..../ /../ / / // //  __// / / /../ __  // /_/ // /_/ /.
/_____/.\__, /.../_/ |_/.\__, / \__,_/ \__, /.\___//_/ /_/.....|___/.\____/..../_/../_/ /_//_/ \___//_/ /_/../_/ /_/.\__,_/.\____/..
......./____/.........../____/......../____/........................................................................................
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 488 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 488 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 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 464 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 460 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 488 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 416 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 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 464 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 460 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 108 ms 348 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 488 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 416 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 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 464 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 460 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 108 ms 348 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 16 ms 3624 KB Output is correct
36 Execution timed out 1035 ms 3928 KB Time limit exceeded
37 Halted 0 ms 0 KB -