Submission #1085046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085046		NVTH	Knapsack (NOI18_knapsack)	C++14	73 / 100	1035 ms	3928 KiB

knapsack

#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 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27