Submission #1154467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154467		deptrais1thegioi	Knapsack (NOI18_knapsack)	C++20	100 / 100	109 ms	36680 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define tn long long
//#define pair pair< tn, tn >
#define thaonguyen( i, a, b ) for( tn i = a; i <= b; i++ )
#define nguyenthao( i, a, b ) for( tn i = a; i >= b; i-- )
const tn N = 1e5 + 5;
const tn M = 2e3 + 5;
vector<pair<tn,tn>> g[N];
tn n, w, j, v, stop , result, cur_cnt, cur_w, cur_val, cur_item, change, a, W, dp[M][M];
void reset(){
    cur_cnt = 0; cur_w = 0; cur_val = 0; cur_item = 0; change = 0;
}
signed main(){
    cin >> W >> n;
    thaonguyen( i, 1, n ){
        cin >> v >> w >> a;
        g[w].push_back( { v, a } );
    }
    thaonguyen( i, 1, W ){
        sort( g[i].begin(), g[i].end(), greater<pair<tn,tn>>() );
        // if ( g[i].size() ) 
        //     cout << i << endl; 
        // for( auto v : g[i] ) 
        //     cout << v.fi << " " << v.se << endl;  
        // if ( g[i].size() ) 
        //     cout << endl;
            thaonguyen( j, 1, W ){
                stop = j / i; reset(); 
                dp[i][j] = dp[i-1][j];
                if ( !g[i].size() )
                    continue;
                if ( stop ){
                    while ( cur_cnt < stop ){
                        change++; cur_cnt++;
                        if ( change > g[i][cur_item].second ){
                            cur_item++;
                            change = 1;
                        }
                        if ( cur_item + 1 > g[i].size() ) 
                            break;
                        cur_val += g[i][cur_item].fi;
                        cur_w   += i;
                        dp[i][j] = max( dp[i][j], dp[i - 1][ j - cur_w ] + cur_val );
                        result = max( result, dp[i][j] ); 
                    }
                }
            } 
    }
    cout << result;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27