Submission #1095242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095242		nmts	Knapsack (NOI18_knapsack)	C++17	100 / 100	69 ms	36500 KiB

knapsack

#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , " r " , stdin),freopen(name".out" , " w " , stdout)
#define faster    ios_base :: sync_with_stdio(false) , cin.tie(0) , cout.tie(0) 
#define pii pair < int , int >
#define fi first
#define se second
#define endl '\n'    
#define ll long long
#define int ll
const int maxn = 5e3 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;
const int block_sz = 316;


template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

using namespace std;

int limit , n;

map<int , vector<pii>> m;

ll ans = 0;

void solve()
{

    cin >> limit >> n ;

    for (int i = 1 ; i <= n ; ++i)
        {
            int v , w , k ; cin >> v >> w >> k ;
            if (w <= limit && k > 0) m[w].push_back(make_pair(v , k));
        }

    vector<vector<ll>>dp(m.size() + 1 , vector<ll>(limit + 1 , -INFLL));


    dp[0][0] = 0;

    int id = 1;
    for (auto&[w , item] : m)
        {

            sort(item.rbegin() , item.rend());

            
            for (int j = 0 ; j <= limit ; ++j)
                {

                    int k = 0;
                    int profit = 0;
                    int cur = 0;
                    dp[id][j] = dp[id - 1][j];
                    
                    int id_item = 0;

                    while (w * (k + 1) <= j && id_item < item.size())
                        {

                            k++;
                            profit += item[id_item].fi;
                            dp[id][j] = max(dp[id][j] , dp[id - 1][j - k * w] + profit);
                            cur++;

                            if (cur == item[id_item].se)    
                                {
                                    cur = 0;
                                    ++id_item;
                                }

                        }
                }
            ++id;

        }

    for (int i = 1 ; i <= limit ; ++i)
        maximize(ans , dp[id - 1][i]);
    

    cout << ans << endl;

}   


int32_t main()
{
    faster;
    // file("txt");
    // int t ; cin >> t ; while (t--)
    solve();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:63:56: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                     while (w * (k + 1) <= j && id_item < item.size())
      |                                                ~~~~~~~~^~~~~~~~~~~~~

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