Submission #861527

#	Time	Username	Problem	Language	Result	Execution time	Memory
861527		vjudge1	Knapsack (NOI18_knapsack)	C++11	73 / 100	1045 ms	3932 KiB

knapsack

/** @author Mihari */

#include <cstdio>
#include <iostream>
#include <cstring>
// using namespace std;

#define USING_FREAD
#define NDEBUG
#include <cassert>

namespace Mihari {

#define rep(i, l, r) for(int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define repf(i, l, r) for (int i = (l), i##_end_ = (r); i < i##_end_; ++i)
#define drep(i, l, r) for(int i = (l), i##_end_ = (r); i >= i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define whole(v) ((v).begin()), ((v).end())
#define bitcnt(s) (__builtin_popcount(s))
/** @warning no forced type conversion */
#define rqr(x) ((x) * (x))
#define y0 FUCK_UP
#define y1 MOTHER_FUCKER
#define masdf(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;

template<class T> inline T fab(T x) { return x < 0 ? -x : x; }
template<class T> inline void chkmin(T& x, const T rhs) { x = std::min(x, rhs); }
template<class T> inline void chkmax(T& x, const T rhs) { x = std::max(x, rhs); }

#ifdef USING_FREAD
inline char qkgetc() {
# define BUFFERSIZE 1 << 20
    static char BUF[BUFFERSIZE], *p1 = BUF, *p2 = BUF;
    return p1 == p2 && (p2 = (p1 = BUF) + fread(BUF, 1, BUFFERSIZE, stdin), p1 == p2) ? EOF : *p1++;
# undef BUFFERSIZE
}
# define CHARRECEI qkgetc()
#else
# define CHARRECEI getchar()
#endif

template<class T> inline T readret(T x) {
    x = 0; int f = 0; char c;
    while (!isdigit(c = CHARRECEI)) if(c == '-') f = 1;
    for (x = (c ^ 48); isdigit(c = CHARRECEI); x = (x << 1) + (x << 3) + (c ^ 48));
    return f ? -x : x;
}
template<class T> inline void readin(T& x) {
    x = 0; int f = 0; char c;
    while (!isdigit(c = CHARRECEI)) if (c == '-') f = 1;
    for (x = (c ^ 48); isdigit(c = CHARRECEI); x = (x << 1) + (x << 3) + (c ^ 48));
    if (f) x = -x;
}
template<class T, class... Args> inline void readin(T& x, Args&... args) {
    readin(x), readin(args...);
}
template<class T> inline void writln(T x, char c = '\n') {
    if (x < 0) putchar('-'), x = -x;
    static int __stk[55], __bit = 0;
    do __stk[++__bit] = static_cast<int>(x % 10), x /= 10; while (x);
    while (__bit) putchar(__stk[__bit--] ^ 48);
    putchar(c);
}

} // namespace Mihari
using namespace Mihari;

const int Maxn = (int)1e5;
const int Maxs = 2000;

int siz, n;
int val[Maxn + 5], wei[Maxn + 5], cnt[Maxn + 5];

inline void input() {
    readin(siz, n);
    rep (i, 1, n) readin(val[i], wei[i], cnt[i]);
}

int g[Maxs + 5], dp[Maxs + 5];
int q[Maxs + 5], op, ed;
inline void getDp() {
    memset(dp, -0x3f, sizeof dp); dp[0] = 0;
    rep (i, 1, n) {
        memcpy(g, dp, siz + 1 << 2);
        // masdf("<----------- Now i == %d -------------->\n", i);
        rep (r, 0, wei[i] - 1) {
            op = 1, ed = 0;
            q[++ed] = r;
            for (int k = 1, cur; (cur = k * wei[i] + r) <= siz; ++k) {
                while ((cur - q[op]) / wei[i] > cnt[i]) ++op;
                // masdf("dp[%d] trans from g[%d](== %d)\n", cur, q[op], g[q[op]]);
                chkmax(dp[cur], g[q[op]] + (cur - q[op]) / wei[i] * val[i]);
                while (op <= ed && (cur - q[op]) / wei[i] * val[i] < g[cur] - g[q[op]]) ++op;
                q[++ed] = cur;
            }
        }
        // masdf("After i == %d\n", i);
        // rep (j, 0, siz) masdf("dp[%d] == %d\n", j, dp[j]);
    }
    int mxx = -1;
    rep (i, 0, siz) chkmax(mxx, dp[i]);
    writln(mxx);
}

signed main() {
    input();
    getDp();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void getDp()':
knapsack.cpp:91:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   91 |         memcpy(g, dp, siz + 1 << 2);
      |                       ~~~~^~~

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