제출 #1354104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1354104		minhmc2019	Knapsack (NOI18_knapsack)	C++17	73 / 100	17 ms	45812 KiB

knapsack

#include <bits/stdc++.h>
#define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
#define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
#define debug(x) cout << "[DEBUG]:  " << #x << " = " << x << endl;
#define log2(x) ((x) > -1 ? __lg((x)) : 0)
#define BITS(x) (1 << (x))
#define int long long
using namespace std;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 30;
const int INF = 1e18;

int S, n;
struct Info {
    int v, w, k;
} A[N];

namespace sub3 {
    bool check() {
        FOR(i, 1, n, 1) {
            if (A[i].k > 10) return false;
        }
        return (n <= 100);
    }
    int dp[105][2005];
    void solve() {
        FOR(i, 1, n, 1) {
            int times  = A[i].k;
            int weight = A[i].w;
            FOR(K, 0, S, 1) {
                dp[i][K] = dp[i - 1][K];
                if (K - weight >= 0) {
                    FOR(t, 1, min(times, K / weight), 1) {
                        if (K - weight * t >= 0) {
                            dp[i][K] = max(dp[i][K], dp[i - 1][K - weight * t] + A[i].v * t);
                        }
                    }
                }
            }
        }
        cout << dp[n][S] << endl;
    }
}

namespace sub4 {
    int dp[3150][2005];
    bool check() {
        FOR(i, 1, n, 1) {
            if (A[i].k > 1e9) return false;
        }
        return (n <= 100);
    }
    void solve() {
        vector <Info> Arr; Arr.reserve(n + 5);
        Arr.push_back({-1, -1, -1});

        FOR(i, 1, n, 1) {
            int values  = A[i].v;
            int weight  = A[i].w;
            int times   = A[i].k;

            FOR(bit, 0, LG, 1) {
                int T = BITS(bit);
                if (times >= T) {
                    times -= T;
                    Arr.push_back({values * T, weight * T, 1});
                }
                else if (times > 0){
                    Arr.push_back({values * times, weight * times, 1});
                    break;
                }
            }
        }
//
        int len = Arr.size() - 1;

        FOR(i, 1, len, 1) {
            int times  = Arr[i].k;
            int weight = Arr[i].w;
            FOR(K, 0, S, 1) {
                dp[i][K] = dp[i - 1][K];
                if (K - weight >= 0) {
                    dp[i][K] = max(dp[i][K], dp[i - 1][K - weight] + Arr[i].v);
                }
            }
        }
        cout << dp[len][S] << endl;
    }
}

void solve() {
    cin >> S >> n;
    FOR(i, 1, n, 1) {
        int v, w, k; cin >> v >> w >> k;
        A[i] = {v, w, k};
    }
    if (sub3::check()) {
        sub3::solve();
    }
    else if (sub4::check()) {
        sub4::solve();
    }
//    else {
//        subAC::solve();
//    }
}

signed main() {
    #define name "task"
    if (ifstream(name".inp")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
}

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 12 / 12
• 서브태스크 2: 17 / 17
• 서브태스크 3: 20 / 20
• 서브태스크 4: 24 / 24
• 서브태스크 5: 0 / 27