Submission #1303679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303679		burstingfire355	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	332 KiB

knapsack

/*
Author - burstingfire355
*/

#include <bits/stdc++.h>
#include <iostream>

const long long mod = 1e9 + 7;
const long long cmod = 998244353;
#define F first

#define S second
#define pb push_back
#define YES cout << "YES\n"
#define NO cout << "NO\n"
using namespace std;



#define ll long long
#define Sort(A) sort(A.begin(), A.end())
#define modq(x) x = ((x % mod) + mod) % mod
#define loop(x, n) for (int i = x; i < n; i++)
#define V vector<int>
#define VV vector<V>
#define rep(i, n) for (ll i = 0; i < (n); ++i)

typedef pair<ll, ll> iPair;

vector<pair<int, int>> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pair<int, int>> dir2 = {{1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
vector<set<int>> adj;
vector<vector<iPair>> adjw;
// vector<pair<int, int>> adjw;
vector<bool> vis;
vector<bool> prime;
vector<int> primenumbers;
vector<bool> inrec;

const int INF = 1e9 + 10;

struct Event
{
    int time, type, id, r;
    bool operator<(const Event &e) const
    {
        if (time == e.time)
            return type > e.type;
        return time < e.time;
    }
};

pair<int, int> findNestedSegments(vector<pair<int, int>> &segments)
{
    int n = segments.size();
    vector<Event> events;

    for (int i = 0; i < n; ++i)
    {
        events.push_back({segments[i].first, 1, i + 1, segments[i].second});
        events.push_back({segments[i].second, -1, i + 1, segments[i].first});
    }

    sort(events.begin(), events.end());

    set<pair<int, int>> activeSegments;

    for (auto &e : events)
    {
        if (e.type == 1)
        {
            auto it = activeSegments.lower_bound({e.r, 0});
            if (it != activeSegments.end())
            {
                return {e.id, it->second};
            }
            activeSegments.insert({e.r, e.id});
        }
        else
        {
            activeSegments.erase({e.time, e.id});
        }
    }

    return {-1, -1};
}

class SegmentTree
{
    vector<int> tree;
    vector<int> lazy;
    int n;

public:
    SegmentTree(const vector<int> &arr)
    {
        n = arr.size();
        tree.resize(4 * n);
        lazy.resize(4 * n, 0);
        build(arr, 0, 0, n - 1);
    }

    void build(const vector<int> &arr, int node, int start, int end)
    {
        if (start == end)
        {
            tree[node] = arr[start];
        }
        else
        {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    void propagate(int node, int start, int end)
    {
        if (lazy[node] != 0)
        {
            tree[node] += lazy[node];
            if (start == end && tree[node] < 0)
                tree[node] = 0;

            if (start != end)
            {
                lazy[2 * node + 1] += lazy[node];
                lazy[2 * node + 2] += lazy[node];
            }

            lazy[node] = 0;
        }
    }

    void rangeUpdate(int l, int r, int val, int node, int start, int end)
    {
        propagate(node, start, end);

        if (r < start || end < l)
            return;

        if (l <= start && end <= r)
        {
            lazy[node] += val;
            propagate(node, start, end);
            return;
        }

        int mid = (start + end) / 2;
        rangeUpdate(l, r, val, 2 * node + 1, start, mid);
        rangeUpdate(l, r, val, 2 * node + 2, mid + 1, end);
        tree[node] = (tree[2 * node + 1] + tree[2 * node + 2]);
    }

    int rangeQuery(int l, int r, int node, int start, int end)
    {
        propagate(node, start, end);

        if (r < start || end < l)
            return 0;

        if (l <= start && end <= r)
            return tree[node];

        int mid = (start + end) / 2;
        int left = rangeQuery(l, r, 2 * node + 1, start, mid);
        int right = rangeQuery(l, r, 2 * node + 2, mid + 1, end);
        return min(left, right);
    }

    void updateRange(int l, int r, int val)
    {
        rangeUpdate(l, r, val, 0, 0, n - 1);
    }

    int queryRange(int l, int r)
    {
        return rangeQuery(l, r, 0, 0, n - 1);
    }
};

struct fenwicktree
{

    int n;
    vector<int> bits;

    fenwicktree(int n)
    {
        bits.resize(n, 0);
    }

    void update(int val)
    {

        while (val < n)
        {
            bits[val] += 1;
            val += (val & (-val));
        }
    }

    int sum(int idx)
    {

        int sum = 0;

        while (idx > 0)
        {
            sum += bits[idx];
            idx -= (idx & (-idx));
        }

        return sum;
    }

    int query(int l, int r)
    {
        if (l > r)
        {
            return 0;
        }

        return sum(r) - sum(l - 1);
    }
};
struct DSU
{
    int n;
    vector<int> parent;
    vector<int> rank;
    vector<int> size;
    vector<int> count;
    DSU(int n)
    {
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        count.resize(n + 1, 0);

        for (int i = 1; i <= n; i++)
        {

            parent[i] = i;
        }
    }

    int find_set(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = find_set(parent[x]);
        }

        return parent[x];
    }

    void union_set(int x, int y)
    {
        int px = find_set(x);
        int py = find_set(y);
        if (px != py)
        {
            if (size[px] < size[py])
            {
                swap(px, py);
            }
            parent[py] = px;
            size[px] += size[py];
            count[px] += count[py];
        }
    }
};

int leftmost(ll n)
{

    int pos = 0;
    while (n > 0)
    {
        n >>= 1;
        pos++;
    }
    return pos - 1;
}

int findMSBPosition(long long n)
{
    if (n == 0)
        return -1;
    return (int)(log2(n));
}

ll binpow(ll a, ll n, ll mod)
{
    ll res = 1;
    while (n != 0)
    {
        if (n & 1)
        {
            res *= a;
            res %= mod;
        }
        a *= a;
        a %= mod;
        n >>= 1;
    }
    return res % mod;
}

ll inv(ll x, ll mod)
{
    if (x % mod == 0)
        return 0;
    return binpow(x, mod - 2, mod);
}

ll query(int &a, int &b)
{

    cout << a << " " << b << endl;
    int cnt;
    cin >> cnt;
    return cnt;
}

bool compare(const tuple<int, int, int> &a, const tuple<int, int, int> &b)
{
    if (get<0>(a) != get<0>(b))
        return get<0>(a) > get<0>(b);
    if (get<1>(a) != get<1>(b))
        return get<1>(a) > get<1>(b);
    return get<2>(a) > get<2>(b);
}
void initprime(int n)
{
    prime.resize(n + 1, true);

    prime[1] = prime[0] = false;

    for (int i = 2; i * i <= n; i++)
    {

        if (prime[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                prime[j] = false;
            }
        }
    }

    // for (int i = 2; i <= n; i++)
    // {
    //     if (prime[i])
    //     {
    //         primenumbers.push_back(i);
    //     }
    // }
}

bool isPerfectSquare(long long int x)
{
    if (x >= 0)
    {
        int sr = sqrt(x);
        return (sr * sr == x);
    }
    return false;
}
int countPS(string str)
{
    int N = str.length();

    int cps[N + 1][N + 1];
    memset(cps, 0, sizeof(cps));

    for (int i = 0; i < N; i++)
        cps[i][i] = 1;

    for (int L = 2; L <= N; L++)
    {
        for (int i = 0; i <= N - L; i++)
        {
            int k = L + i - 1;
            if (str[i] == str[k])
                cps[i][k] = cps[i][k - 1] + cps[i + 1][k] + 1;
            else
                cps[i][k] = cps[i][k - 1] + cps[i + 1][k] - cps[i + 1][k - 1];
        }
    }

    return cps[0][N - 1];
}

void calculate(int n, string &s, vector<int> &lps)
{

    for (int i = 1; i < n; i++)
    {

        int j = lps[i - 1];

        while (j > 0 && s[i] != s[j])
        {
            j = lps[j - 1];
        }

        if (s[i] == s[j])
        {
            j++;
        }

        lps[i] = j;
    }
}

vector<ll> dijkstra(int n, int src, ll x)
{
    vector<ll> dist(n + 1, INF);

    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty())
    {
        int u = pq.top().second;
        ll currDist = pq.top().first;
        pq.pop();

        for (const auto &neighbor : adjw[u])
        {
            int v = neighbor.first;
            int weight = neighbor.second;
            ll adjustedWeight;
        }
    }

    return dist;
}
int log_a_to_base_b(int a, int b)
{
    return log2(a) / log2(b);
}

ll prim(int n)
{
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    vector<bool> vis(n + 1, false);
    ll maxEdge = 0;

    pq.push({0, 0});

    while (!pq.empty())
    {
        auto [weight, u] = pq.top();
        pq.pop();

        if (vis[u])
            continue;

        vis[u] = true;
        maxEdge = max(maxEdge, weight);

        for (auto [v, w] : adjw[u])
        {
            if (!vis[v])
                pq.push({(ll)w, v});
        }
    }

    return maxEdge;
};

struct p
{
    ll v, w, k;
};
int main()
{
    ios::sync_with_stdio(0);

    cin.tie(0);
    cout.tie(0);

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t;
    t = 1;

    while (t--)
    {

        int s, n;
        cin >> s >> n;

        vector<ll> dp(s + 1, -1);
        dp[0] = 0;

        for (int idx = 0; idx < n; idx++)
        {
            ll v, w, k;
            cin >> v >> w >> k;

            ll mul = 1;
            while (k > 0)
            {
                ll take = min(mul, k);
                k -= take;
                ll Val = v * take;
                ll W = w * take;
                for (int i = s; i >= W; i--)
                {
                    if (dp[i - W] != -1)
                    {
                        dp[i] = max(dp[i], dp[i - W] + Val);
                    }
                }
            }
        }

        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:489:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  489 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:490:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  490 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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