Submission #976131

#	Time	Username	Problem	Language	Result	Execution time	Memory
976131		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	120 ms	124240 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"

const int N = 2e3 + 5;

vector < pair < int, int > > a(1, {0, 0}), yes[N];

int n , s;

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

    cin >> s >> n;

    for ( int i = 1; i <= n; i++){
        int harga, berat, stok; cin >> harga >> berat >> stok;
        yes[berat].push_back({harga, stok});
    }

    for ( int i = 1; i <= 2000; i++) sort ( yes[i].begin(), yes[i].end(), greater<pair < int, int >>());

    for ( int i = 1; i <= 2000; i++){
        int can = 2000;

        for ( int j = 0; j < yes[i].size(); j++){
            for ( int k = 1; k <= yes[i][j].second; k++){
                if ( can - i < 0 ) break;
                a.push_back({i, yes[i][j].first});

                can -= i;
                // berat, harga
            }
        }
    }

    // 2e3 . log ( 2e3 ) . 2e3

    //for ( int i = 1; i < a.size(); i++) cout << a[i].first << " " << a[i].second <<  endl;
    //cout << endl;

    vector < vector < int > > dp ( a.size() + 5, vector < int > ( s + 5, 0 ));

    for ( int i = 1; i < a.size(); i++){
        for ( int j = 0; j <= s; j++){
            dp[i][j] = dp[i-1][j];
            if ( j >= a[i].first ){
                dp[i][j] = max ( dp[i][j], dp[i - 1][j - a[i].first] + a[i].second);
            }
        }
    }

    cout << dp[a.size() - 1][s];
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:27:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for ( int j = 0; j < yes[i].size(); j++){
      |                          ~~^~~~~~~~~~~~~~~
knapsack.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for ( int i = 1; i < a.size(); i++){
      |                      ~~^~~~~~~~~~

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