제출 #1104972

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

knapsack

#pragma GCC optimize("Ofast","unroll-all-loops","fast-math","no-stack-protector")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define alls(x) x.begin(), x.end()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define rep(i, n) for (int i = 1; i <= int(n); i++)
#define sz(x) int(x.size())
#define dbg(x) cerr << #x << " = " << x << endl;
#define cin std::cin
#define cout std::cout
#define pii pair<int, int>
#define pll pair<ll, ll>ip
const ld eps = 1e-12;
const ll inf = 1e16;
const ll mod = 998244353;
const ll mod1 = 1e9 + 87;
const ll mod2 = 1e9 + 93;
using namespace std;

void IOS(string name = "") {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false); // see /general/fast-io
    if (sz(name)) {
        freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

const int maxn = 3e6 + 3e5;
int cnt = 0;
ll wei[maxn], val[maxn];

int main() {
    IOS();
    int n, W;
    cin >> W >> n;
    rep(i, n) {
        int v, w, m;
        cin >> v >> w >> m;
        int c = 1;
        while (m > c) {
            m -= c;
            wei[++cnt] = 1ll * w * c;
            val[cnt] = 1ll * v * c;
            c *= 2;
        }
        wei[++cnt] = 1ll * w * m;
        val[cnt] = 1ll * v * m;
    }
    vector<ll> dp(W + 1, 0);
    rep(i, cnt) {
        for (int j = W; j >= wei[i]; j--) {
            dp[j] = max(dp[j], dp[j - wei[i]] + val[i]);
        }
    }
    cout << dp[W] << endl;
    return 0;
}

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

knapsack.cpp: In function 'void IOS(std::string)':
knapsack.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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