Submission #892806

#	Time	Username	Problem	Language	Result	Execution time	Memory
892806		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	1061 ms	18380 KiB

knapsack

#include <bits/stdc++.h>  
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, W; vector<p64> b; ll dp[N];
void readata(){
    cin >> W >> n;
    for (int i = 1; i <= n; ++i){
        int w, v, a; cin >> v >> w >> a;
        for (int i = 1; i <= a; i *= 2){
            if (a >= i){
                b.push_back({w * i, v * i});
                a -= i;
            }
        }
        if (a > 0){
            b.push_back({w * a, v * a});
        }
    }
}
signed main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r", stdin);
    // freopen("output.txt","w", stdout);
    // #endif
    fast_cin();
    readata();
    ll ans = 0;
    for (int i = 0; i < b.size(); ++i){
        for (int j = W; j >= b[i].fi; --j){
            dp[j] = max(dp[j], dp[j - b[i].fi] + b[i].se);
            ans = max(ans, dp[j]);
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:49:23: 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]
   49 |     for (int i = 0; i < b.size(); ++i){
      |                     ~~^~~~~~~~~~

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