Submission #954247

#	Time	Username	Problem	Language	Result	Execution time	Memory
954247		pro_coder_123	Knapsack (NOI18_knapsack)	C++17	73 / 100	58 ms	7656 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int INF = (int)(1e9)+2;
const int mod1 = (int)(1e9)+7;

bool isprime(int n){
    if(n==1)
        return 0;
    for(int i=2;i<=(int)(sqrt(n));i++){
        if(n%i==0)
            return 0;
    }
    return 1;
}

int moduloinverse(int a,int p){
    int power=p-2;
    int curr=a;
    int ans=1;
    while(power>0){
        if(power & 1)
            ans=((ans%p)*(curr%p))%p;
        curr=((curr%p)*(curr%p))%p;
        power/=2;
    }
    return ans%p;
}

int binexp(int a,int b,int m){
    int ans=1;
    int curr=a;
    while(b>0){
        if(b&1)
            ans=((ans%m)*(curr%m))%m;
        curr=((curr%m)*(curr%m))%m;
        b/=2;
    }
    return ans%m;
}

int __lcm(int a,int b){
    return (a*b)/__gcd(a,b);
}

/*****************************TOTIENT FUNCTION***********************************/
//totient function
//TC->O(sqrt(n))
int phi(int n){
//phi(n)=number of integers from 1 to n inclusive that are co prime to n
//phi(p)=p-1, p->prime
//phi(p^k)=p^k-p^(k-1), p->prime, k>=1
//phi(ab)=phi(a)*phi(b)*d/phi(d), d->gcd(a,b)              //todo
//phi(n)=n(1-1/p1)(1-1/p2)....(1-1/pk)
int result = n;
for(int i=2;i*i<=n;i++){
    if(n%i == 0){
        while(n%i == 0){
            n=n/i;
        }
        result-=result/i;
    }
}
if(n>1){
result-=result/n;
}
return result;
}

//totient function sieve
//TC->O(nloglogn)
vector<int> phiv;
void phi1_n(int n){
    phiv.resize(n+1);
    for(int i=0;i<=n;i++){
        phiv[i]=i;
    }
    for(int i=2;i<=n;i++){
        if(phiv[i]==i){
            for(int j=i;j<=n;j+=i){
                phiv[j]-=phiv[j]/i;
            }
        }
    }
}

//divisor sum property: summation phi(d)=n , d|n
//Euler theorem a^(phi(m)) = 1 (mod m)
/*******************************END**********************************/

/***************************SEGMENT TREE*****************************/
vector<ll> seg;
vector<ll> lazy;
void initseg(int n){
seg.assign(4*n+4,0);
lazy.assign(4*n+4,0);
}

void buildseg(vector<ll>& a,ll idx,ll l,ll r) {
if (l == r) seg[idx] = a[l];
else {
ll mid = (l + r) / 2;
buildseg(a, idx*2, l, mid);
buildseg(a, idx*2+1, mid+1, r);
seg[idx] = seg[idx*2] + seg[idx*2+1]; // change function here
}
}

void push(ll idx,ll l,ll r){
// Default : addition operation
ll mid = (l+r)/2;
seg[2*idx]+=(mid-l+1)*lazy[idx];
lazy[2*idx]+=lazy[idx];
seg[2*idx+1]+=(r-mid)*lazy[idx];
lazy[2*idx+1]+=lazy[idx];
lazy[idx]=0; // change identity here
}

ll queryseg(ll idx,ll l,ll r,ll lq,ll rq) {
if (l>rq || r<lq) return 0; //change identity here
if (l>=lq && r<=rq) return seg[idx];
push(idx,l,r);
ll mid = (l + r) / 2;
return queryseg(idx*2, l, mid, lq, rq) + queryseg(idx*2+1, mid+1, r, lq, rq); //change function here
}

void updateseg(ll idx,ll l,ll r,ll pos,ll new_val) {
if (l == r) seg[idx] = new_val;                 //change depending on type of update
else {
ll mid = (l + r) / 2;
if (pos <= mid) updateseg(idx*2, l, mid, pos, new_val);
else updateseg(idx*2+1, mid+1, r, pos, new_val);
seg[idx] = seg[idx*2] + seg[idx*2+1]; // change function here
}
}

void upranseg(ll idx,ll l,ll r,ll lu,ll ru,ll addend) {
// Default: addition update operation, sum query operation
if (l>ru || r<lu) return;
if (l>=lu && r<=ru) {
seg[idx] += (r-l+1)*addend; // change function here
lazy[idx] += addend; // change function here
}
else {
push(idx,l,r);
ll mid = (l + r) / 2;
upranseg(idx*2, l, mid, lu, ru, addend);
upranseg(idx*2+1, mid+1, r, lu, ru, addend);
seg[idx] = seg[idx*2] + seg[idx*2+1]; // change function here
}
}

/*********************************END****************************************/

/********************POLYNOMIAL ROLLING HASH FUNCTION************************/

int compute_hash(string &s){
int mod = (int)(1e9)+9;
int p = 31;
int hash_val = 0;
int p_pow=1;
for(auto ch : s){
hash_val=(hash_val+((ch-'a'+1)*p_pow)%mod)%mod;
p_pow=(p_pow*p)%mod;
}
return hash_val;
}

int count_unique_substrings(string &s){
//TC->O(n^2)
    int n = s.size();
    vector<int> p_pow(n);
    p_pow[0]=1;
    int p=31;
    int m = (int)(1e9)+9;
    for(int i=1;i<n;i++)
    p_pow[i]=(p_pow[i-1]*p)%m;
    vector<int> hashes(n+1,0);  //hashes[i] stores the prefix hash of first i characters
    hashes[0]=0;
    for(int i=0;i<n;i++){
        hashes[i+1]=(hashes[i]+((s[i]-'a'+1)*p_pow[i])%m)%m;
    }
    int cnt=0;
    for(int l=1;l<=n;l++){
        set<int> hs;
        for(int i=0;i<=n-l;i++){
            int curr_hash=(hashes[i+l]-hashes[i]+m)%m;
            curr_hash=(curr_hash*p_pow[n-i-1])%m;
            hs.insert(curr_hash);
        }
        cnt+=hs.size();
    }
    return cnt;
}

/************************************END*************************************/

/**************************************LIS**************************************/
// int lis(vector<int>&a){         //1-indexed     size(a)=n+1
// int n = a.size()-1;
// vector<int> helper;         //helper[i]     gives minimum last value for an lis of length i
// for(int i=1;i<=n;i++){
// if(helper.empty() || helper.back()<a[i]){
//     helper.push_back(a[i]);
// }
// else{
// auto it = lower_bound(helper.begin(),helper.end(),a[i]);
// *(it)=a[i];
// }
// }
//     return helper.size();
// }

/***************************************END**************************************/

/***************************LCA-BINARY LIFTING**********************************/
//vector<vector<int>> up;
//vector<vector<int>> g;
//vector<pair<int,int>> tt;
//int l;
// void initlca(int n){
// tt.clear();
// up.clear();
//     tt.resize(n+1);
//     l = ceil(log2(n));
//     up.resize(n+1,vector<int>(l+1,-1));
//}

// void dfslca(int node,int parent,int &ti){           //initially node=parent=1;ti=0;
//     up[node][0]=parent;
//     tt[node].first=ti;
//     for(int i=1;i<=l;i++){
//         up[node][i]=up[up[node][i-1]][i-1];
//     }
//     ti++;
//     for(auto neigh : g[node]){
//         if(neigh!= parent){
//             dfslca(neigh,node,ti);
//         }
//     }
//     tt[node].second=ti;
//     ti++;
// }

// int check(int a,int b){
//     if(tt[a].first<=tt[b].first && tt[a].second>=tt[b].second) return 1; return 0;
// }

// int lca(int a,int b){
//     if(check(a,b)){
//         return a;
//     }
//     if(check(b,a)){
//         return b;
//     }
//     int st=l;
//     int anc=a;
//     while(st>-1 && (!(check(anc,b)==0 && check(up[anc][0],b)==1))){
//         if(check(up[anc][st],b)){
//             st--;
//         }
//         else{
//             anc=up[anc][st];
//             st--;
//         }
//     }
//     return up[anc][0];
// }

/**********************************END*************************************/

// struct minstack{
//     stack<pair<int,int>> st;
//     int getmin() {return st.top().second;}
//     bool empty() {return st.empty();}
//     void push(int ele){
//         int mini=ele;
//         if(!empty()){
//             mini=min(mini,st.top().second);
//             st.push({ele,mini});
//         }
//     }
//     void pop(){
//         st.pop();
//     }
//     int top(){
//         return st.top().first;
//     }
// };

// struct minqueue{
//     stack<pair<int,int>> s1,s2;
//     int getmin(){
//         int mini;
//         if(s1.empty() || s2.empty()){
//             mini = (s1.empty())?(s2.top().second):(s1.top().second);
//         }
//         else{
//             mini=min(s1.top().second,s2.top().second);
//         }
//         return mini;
//     }
//     void push(int ele){
//         int mini;
//         mini = (s1.empty())?(ele):(min(ele,s1.top().second));
//         s1.push({ele,mini});
//     }
//     void pop(){
//         if(s2.empty()){
//             while(!s1.empty()){
//                 int element = s1.top().first;
//                 s1.pop();
//                 int newmini;
//                 newmini = (s2.empty())?(element):(min(element,s2.top().second));
//                 s2.push({element,newmini});
//             }
//         }
//         int remove_element=s2.top().first;
//         s2.pop();
//     }
// };

int dp[2001][2001];

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        int s,n;
        cin>>s>>n;
        vector<int> cnt;
        vector<vector<int>> values;
        vector<set<pair<int,int>,greater<pair<int,int>>>> v(s+1);

        for(int i=1;i<=n;i++){
            int vi,w,k;
            cin>>vi>>w>>k;
            cnt.push_back(w);
            v[w].insert({vi,k});
        }

        cnt.push_back(-1);
        // for(auto i : cnt){
        //     cout<<i<<endl;
        // }
        // cout<<"Hi"<<endl;
        sort(cnt.begin(),cnt.end());
        auto it  = unique(cnt.begin(),cnt.end());
        cnt.resize(distance(cnt.begin(),it));
        int num=cnt.size()-1;
        values.resize(num+1);

        // cout<<num<<endl;

        for(int i=1;i<=num;i++){
            for(auto j : v[cnt[i]]){
                int flag=0;
                for(int k=0;k<j.second;k++){
                    values[i].push_back(j.first);
                    if(values[i].size()==2000){
                        flag=1;
                        break;
                    }
                }
                if(flag){
                    break;
                }
            }
        }

        // for(int i=1;i<=num;i++){
        //     cout<<i<<endl;
        //     for(auto j : values[i]){
        //         cout<<j<<" ";
        //     }
        //     cout<<endl;
        // }

        // cout<<"*****"<<endl;


        for(int i=0;i<=num;i++){
            for(int j=0;j<=s;j++){
                if(i==0){
                    dp[i][j]=0;
                    continue;
                }
                if(j==0){
                    dp[i][j]=0;
                    continue;
                }
                else{
                    dp[i][j]=dp[i-1][j];
                    int temp=0;
                    if(j>=cnt[i]){
                        for(int l=0;l<(j/cnt[i]);l++){
                            if(l>=values[i].size()){
                                break;
                            }
                            temp+=values[i][l];
                            dp[i][j]=max(dp[i][j],dp[i-1][j-(l+1)*cnt[i]]+temp);
                        }
                    }
                }
            }
            // for(int j=0;j<=s;j++){
            //     cout<<i<<" "<<j<<endl;
            //     cout<<dp[i][j]<<endl;
            // }
        }

        cout<<dp[num][s]<<endl;
                
    }
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:403:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  403 |                             if(l>=values[i].size()){
      |                                ~^~~~~~~~~~~~~~~~~~

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