Submission #884453

#	Time	Username	Problem	Language	Result	Execution time	Memory
884453		jonnnnnnnn	Knapsack (NOI18_knapsack)	C++17	100 / 100	76 ms	36680 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>



// Define Template          Python++
// Math
const long double PI = acos(-1);
#define intlen(num)         to_string(num).size()
// Data Structure and Algorithm
#define all(vec)            (vec).begin(),(vec).end()
#define arrsize(arr)        sizeof(arr)/sizeof(int)
#define sortarr(arr)        sort(arr,arr+arrsize(arr));
#define sortvec(vec)        sort(all(vec));
#define minarr(arr)         *min_element(arr,arr+arrsize(arr))
#define minvec(vec)         *min_element(all(vec))
#define maxarr(arr)         *max_element(arr,arr+arrsize(arr))
#define maxvec(vec)         *max_element(all(vec))
#define sumarr(arr)         accumulate(arr,arr+arrsize(arr),0LL)
#define sumvec(vec)         accumulate(all(vec),0LL)
#define reversearr(arr)     reverse(arr,arr+arrsize(arr));
#define reversevec(vec)     reverse(all(vec));
#define range(i,s,e)        for(int i=s;i<e;i++)
#define range2(i,s,e)       for(int i=s;i>=e;i--)
#define fors(var,arr)       for(auto &var:arr)
// Input Output Manage
#define endl "\n"
#define debug(x)    cout<<(#x)<<" : "<<(x)<<endl;
#define debughere cout << "HERE\n";
#define test        cout<<"test"<<endl;
#define fastIO              ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define floatprecision      cout<<fixed<<setprecision(9);
#define fileread            freopen("input.txt","r",stdin);
#define fileout             freopen("output.txt","w",stdout);
#define query               cin>>QUERY;while(QUERY--)
#define inputarr(arr,am)    int arr[am];fors(num,arr)cin>>num;
#define inputvec(vec,am)    vector<int> vec(am);fors(num,vec)cin>>num;
#define input(var)          int var;cin>>var;
#define input2(a,b)         int a,b;cin>>a>>b;
#define make_edge(a,b)      input2(a,b); adj[a].pb(b); adj[b].pb(a);
#define inputs(var)         string var;cin>>var;
#define print(var)          cout<<(var)<<endl;
#define prints(var)         cout<<(var)<<" ";
#define print2(var1,var2)   cout<<(var1)<<" "<<(var2)<<endl;
#define printp(paired)      cout<<(paired.first)<<" "<<(paired.second)<<endl;
#define printyes(cond)      cout<<((cond)?"YES":"NO")<<endl;
#define printarr(arr)       fors(num,arr){cout<<num<<" ";};cout<<endl;
#define printmap(hashmap)   for(auto[x,y]:hashmap)cout<<x<<" : "<<y<<endl;
#define endline             cout<<endl;
// Macro
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define mii map<int,int>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pq priority_queue
#define mp make_pair
#define ms multiset
typedef complex<long long> Point;
#define X real()
#define Y imag()
// Oneliner Function
ll sigma(ll num){return (num*(num+1))/2;}
ll gcd(ll a, ll b){return (a==0?b:gcd(b%a,a));}
ll lcm(ll a, ll b){return (a*b)/gcd(a,b);}
ll binpow(ll a,ll b,ll m=INT64_MAX){ll r=1;a%=m;while(b){if(b&1)r=(r*a)%m;a=(a*a)%m;b>>=1;}return r;}
ll invmod(ll a,ll m){return gcd(a,m)==1?binpow(a,m-2,m):0;}
ll lsb(ll x){return log2(x&-x)+1;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define int long long
#define float long double
int QUERY;
// Constant
const int MOD = 1e9+7;
const long long INF = 1e18;
const int maxn = 2e5+5;


struct DSU {
    vector<int> e;
    DSU(int N) { e = vector<int>(N+10, -1); }

    // get representive component (uses path compression)
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

    bool same_set(int a, int b) { return get(a) == get(b); }

    int size(int x) { return -e[get(x)]; }

    bool unite(int x, int y) {  // union by size
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return true;
    }
};

int checkPrime(int n){ // O( sqrt(N))
    if(n < 2) return false;
    for(int i = 2;i<= sqrt(n);i++){
        if(n%i == 0){
            return false;
        }
    }

    return true;
}


struct primeStruct{
    vector<int> prime_vi;
    bool isprime[maxn];
    int prime_factorization[maxn];

    primeStruct(){
        for(int i = 0;i < maxn;i++){
            isprime[i] = 1;
            prime_factorization[i] = 0;
        }
    }

    void preprocess(){ // O( n log log (n) )
        isprime[0] = 0;
        isprime[1] = 0;
        for(int i = 0;i < maxn;i++){
            if(isprime[i]){
                int cnt = 2;
                prime_factorization[i] = i;
                while(cnt * i < maxn){
                    prime_factorization[i*cnt] = i;
                    isprime[i*cnt] = 0;
                    cnt++;
                }
            }
        }
        for(int i = 0;i < maxn;i++) if(isprime[i]) prime_vi.pb(i);
    }

    vector<int> prime_factorization_vi(int n){
        vector<int> temp;
        while(n!= 1){
            temp.pb(prime_factorization[n]);
            n/= prime_factorization[n];
        }
        return temp;
    }



};

struct segmentTree{
    int segment[1 << 20];
    int arr[maxn];

    void pointUpdate(int idx, int l, int r, int t, int val){
        if(l ==r && r == t) segment[idx] = val;
        else if(l > t | r < t) return;
        else{
            int mid = (l+r)/2;
            pointUpdate(2*idx,l,mid,t,val);
            pointUpdate(2*idx + 1,mid+1,r,t,val);
            segment[idx] = segment[idx*2] + segment[idx*2 + 1]; // fix this if you want to change the type of relation
        }
    }

    int getSum(int idx, int l, int r, int tl, int tr){
        if(l > tr || r < tl) return 0;
        else if(tl <= l && r <= tr) return segment[idx];
        else{
            int mid = (l+r)/2;
            return getSum(2*idx,l,mid,tl,tr) + getSum(2*idx + 1,mid+1,r,tl,tr);
        }
    }



};





void open(){
    freopen("haybales.in", "r", stdin);
    freopen("haybales.out", "w", stdout);
}

struct matrix {
    long long mat[205][205] = {0};
    matrix friend operator *(const matrix &a, const matrix &b){
        matrix c;
        for (int i = 0; i < 205; i++) {
          for (int j = 0; j < 205; j++) {
              c.mat[i][j] = 0;
              for (int k = 0; k < 205; k++) {
                  c.mat[i][j] =(c.mat[i][j]+ a.mat[i][k] * b.mat[k][j])%MOD;
              }
          }
        }
        return c;
    }
};

matrix matpow(matrix &base, long long n) {
    matrix ans = base;
    n--;

    while (n) {
        if(n&1)
            ans = ans*base;
        base = base*base;
        n >>= 1;
    }

    return ans;
}



void solve(){
    int dp[2005][2005];
    range(i,0,2005) range(j,0,2005) dp[i][j]= -INF;


    input2(s,n)
    map<int,vector<pii>> mp;
    range(i,1,n+1){
        input2(v,w)
        input(k)
        if(w <= s) mp[w].pb({v,k});
    }

    dp[0][0] = 0; // the cost of using 0 item to generate a sum of item-weight 0 is 0

    int i = 1;
    for(auto &[weight,items] : mp){

        sort(items.begin(),items.end(),greater<pii>());
        range(j,0,s+1){
            dp[i][j] = dp[i-1][j];

            // we can start simulating
            int count_items = 0;
            int count_each = 0;
            int profit = 0;
            int index_type = 0;
            while((count_items+1)*weight <= j && index_type < items.size()){
                count_items++; // add items
                profit += items[index_type].first; // add second one
                count_each++;

                // if we already used all  of them
                if(count_each == items[index_type].second){
                    count_each = 0;
                    index_type++;
                }

                // construct to previous

                if(dp[i-1][j-(count_items)*weight] != -INF){
                    // the state can be reached
                    dp[i][j] = max(dp[i][j],dp[i-1][j-count_items*weight]+ profit);
                }
            }
        }
        i++;
    }

    int ans = -INF;
    range(j,0,s+1){
        ans = max(ans,dp[i-1][j]);
    }

    print(ans)
}


int32_t main(){
    fastIO


     solve();


    return 0;
}

Compilation message (stderr)

knapsack.cpp: In member function 'void segmentTree::pointUpdate(long long int, long long int, long long int, long long int, long long int)':
knapsack.cpp:168:19: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
  168 |         else if(l > t | r < t) return;
      |                 ~~^~~
knapsack.cpp: In function 'void solve()':
knapsack.cpp:258:61: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |             while((count_items+1)*weight <= j && index_type < items.size()){
      |                                                  ~~~~~~~~~~~^~~~~~~~~~~~~~
knapsack.cpp: In function 'void open()':
knapsack.cpp:195:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |     freopen("haybales.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:196:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |     freopen("haybales.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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