Submission #1092765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092765		JeffLegendPower	Knapsack (NOI18_knapsack)	C++17	73 / 100	1048 ms	1652 KiB

knapsack

// https://oj.uz/problem/view/NOI18_knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define plli pair<ll, int>
#define pll pair<ll, ll>
#define pii pair<int, int>
// Usage: FOR(i, 0, N) {...}
#define FOR(i, start, end) for(int i = start; i < end; i++)

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

struct comp {
    bool operator() (plli a, plli b) {
        return a < b;
    }
};

typedef tree<plli, null_type, comp, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;


// Segtree start
const int Nmax = 1e5;  // limit for array size
int N;  // array size
int t[2 * Nmax];

int oper(int a, int b) {
    return a + b;
}

void build() {  // build the tree
  for (int i = N - 1; i > 0; --i) t[i] = oper(t[i<<1], t[i<<1|1]);
}

void modify(int p, int value) {  // set value at position p
  for (t[p += N] = value; p > 1; p >>= 1) t[p>>1] = oper(t[p], t[p^1]);
}

int query(int l, int r) {  // on interval [l, r)
  int res = 0;
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = oper(res, t[l++]);
    if (r&1) res = oper(res, t[--r]);
  }
  return res;
}
// Segtree end

int main() {
    // Comment out for interactive problems
    ios::sync_with_stdio(false);
	cin.tie(nullptr);

    int S, N;
    cin >> S >> N;

    ll dp[S + 1][2];
    for (int i = 0; i <= S; i++) {
        dp[i][0] = 0;
        dp[i][1] = 1;
    }

    for (int n = 0; n < N; n++) {
        ll V, K;
        int W;
        cin >> V >> W >> K;

        for (int i1 = 0; i1 < W; i1++) {
            deque<pll> q;
            int idx = 0;

            for (int i2 = i1; i2 <= S; i2 += W) {
                while (!q.empty() && idx - q.front().second > K) q.pop_front();

                if (!q.empty()) {
                    pll cur = q.front();
                    ll val = cur.first + (idx - cur.second) * V;

                    dp[i2][(n+1)%2] = max(dp[i2][n%2], val);
                } else dp[i2][(n+1)%2] = dp[i2][n%2];

                ll cur = dp[i2][n%2];
                while (!q.empty() && (q.back().first + (idx - q.back().second) * V) < cur) q.pop_back();
                q.push_back({cur, idx});

                idx++;
            }
        }
    }

    ll most = 0;
    for (int i = 0; i <= S; i++) {
        most = max(most, dp[i][N%2]);
    }
    
    cout << most;
}

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:18:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:19:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  freopen((s + ".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