제출 #1341225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1341225		kiengyt	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	448 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 10;
typedef pair<int, int> pii;
typedef pair<ll, int> pill;
#define fi first
#define se second
const int N = 100005;
int s, n;
int v[N], w[N], k[N];
vector <pair<ll,ll>> doVat;
ll power2[40];
ll dp[2][2005];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    power2[0] = 1;
    for(int i=1;i<=45;i++){
        power2[i] = power2[i-1] * 2;
    }
    cin >> s >> n;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i] >> k[i];

    for(int i=1;i<=n;i++){
        int soDo = k[i];
        for(int j=0;j<=15;j++){
            if(soDo - power2[j] < 0) break;
            doVat.push_back({power2[j] * v[i], power2[j] * w[i]});
            soDo -= power2[j];
        }
        if(soDo > 0){
            doVat.push_back({soDo * v[i], soDo * w[i]});
        }
    }

    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;

    for(int i=0;i<(int)doVat.size();i++){
        for(int j=1;j<=s;j++) dp[(i+1)%2][j] = -1;

        for(int j=0;j<=s;j++){
            if(dp[i%2][j] == -1) continue;
            ll V = doVat[i].fi;
            ll W = doVat[i].se;
            dp[(i+1)%2][j] = max(dp[(i+1)%2][j], dp[i%2][j]);

            if(j + W <= s) dp[(i+1)%2][j + W] = max(1LL*dp[(i+1)%2][j + W], 1LL*dp[i%2][j] + V);
        }
    }
    ll ans = 0;
    for(int j=0;j<=s;j++) ans = max(ans, (ll)dp[(int)doVat.size()%2][j]);
    cout << ans;

    return 0;
}

/*


*/

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'int main()':
knapsack.cpp:23:31: warning: iteration 40 invokes undefined behavior [-Waggressive-loop-optimizations]
   23 |         power2[i] = power2[i-1] * 2;
      |                     ~~~~~~~~~~^
knapsack.cpp:22:18: note: within this loop
   22 |     for(int i=1;i<=45;i++){
      |                 ~^~~~

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