Submission #993121

#	Time	Username	Problem	Language	Result	Execution time	Memory
993121		cpdreamer	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	348 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <utility>
using namespace __gnu_pbds;
using namespace std;

typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;
const int max_n=INT_MAX;
typedef long long  ll;
#define LLM LONG_LONG_MAX
#define pb push_back
#define F first
#define L length()
#define all(v) v.begin(),v.end()
#define  P pair
#define V vector
#define S second
const long long MOD = 1000000007; // 1e9 + 7

void file(){
    freopen("input.txt.txt","r",stdin);
    freopen("output.txt.txt","w",stdout);
}
void setio(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
bool is_sorted(ll A[],ll n) {
    for (ll i = 0; i < n - 1; i++) {
        if (A[i] > A[i + 1])
            return false;
    }
    return true;
}
void solve() {
    ll W, n;
    cin >> W >> n;
    ll v[n], k[n], w[n];
    V<V<P<ll, ll>>> vp(W + 1);
    V<V<P<ll, ll>>> pref(W + 1);
    for (ll i = 0; i < n; i++) {
        cin >> v[i] >> w[i] >> k[i];
        vp[w[i]].pb({v[i], k[i]});
    }
    ll dp[W + 1];
    bool made[W + 1];
    memset(dp, -1, sizeof(dp));
    memset(made, false, sizeof(dp));
    dp[0] = 0;
    made[0] = true;
    for (ll i = 1; i <= W; i++) {
        sort(all(vp[i]));
        reverse(all(vp[i]));
    }
    for (ll i = 1; i <= W; i++) {
        if (!vp[i].empty()) {
            pref[i].pb({vp[i][0].F*vp[i][0].S,vp[i][0].S});
            for (ll j = 1; j < vp[i].size(); j++) {
                pref[i].pb({vp[i][j].F*vp[i][j].S + pref[i][j - 1].F, vp[i][j].S + pref[i][j - 1].S});
            }
        }
    }
    for (ll i = 1; i <= W; i++) {
        if (!vp[i].empty()) {
            for (ll j = W; j >= i; j--) {
                ll weight = j;
                ll l = 0, r = (ll)pref[i].size() - 1;
                ll ans = -1;
                while (l <= r) {
                    ll m = l + (r - l) / 2;
                    if (pref[i][m].S * i >= j) {
                        ans = m;
                        r = m - 1;
                    } else
                        l = m + 1;
                }
                if (ans == -1)
                    ans = (ll) vp[i].size() - 1;
                ll a = 0;
                ll value=0;
                if (ans > 0) {
                    a = (ll) pref[i][ans - 1].S * i;
                    value = (ll) pref[i][ans - 1].F;
                }
                weight -= a;
                ll add = min((weight / i),(ll)vp[i][ans].S);
                a += add*i;
                value+=(ll) vp[i][ans].F * add;
                if (made[j - a]) {
                    made[j] = true;
                    dp[j] = max(dp[j], dp[j - a] + value);
                }
            }
        }
    }
    cout << *max_element(dp, dp + W + 1) << endl;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //file();
    solve();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:59:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for (ll j = 1; j < vp[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~
knapsack.cpp: In function 'void file()':
knapsack.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen("input.txt.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen("output.txt.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void setio(std::string)':
knapsack.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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