oj.uz

Submission #954575

# Submission time Handle Problem Language Result Execution time Memory
954575 2024-03-28T07:24:40 Z pro_coder_123 Knapsack (NOI18_knapsack) C++17
100 / 100
 160 ms 72900 KB 
#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<multiset<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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2648 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2648 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 9 ms 608 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 4 ms 2652 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2648 KB Output is correct
14 Correct 2 ms 2904 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 9 ms 608 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 2 ms 2652 KB Output is correct
22 Correct 2 ms 2652 KB Output is correct
23 Correct 4 ms 2652 KB Output is correct
24 Correct 2 ms 2652 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 12 ms 616 KB Output is correct
27 Correct 2 ms 600 KB Output is correct
28 Correct 0 ms 600 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 5 ms 4188 KB Output is correct
31 Correct 2 ms 2652 KB Output is correct
32 Correct 2 ms 2648 KB Output is correct
33 Correct 2 ms 2852 KB Output is correct
34 Correct 3 ms 2652 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2648 KB Output is correct
14 Correct 2 ms 2904 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 9 ms 608 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 2 ms 2652 KB Output is correct
22 Correct 2 ms 2652 KB Output is correct
23 Correct 4 ms 2652 KB Output is correct
24 Correct 2 ms 2652 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 12 ms 616 KB Output is correct
27 Correct 2 ms 600 KB Output is correct
28 Correct 0 ms 600 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 5 ms 4188 KB Output is correct
31 Correct 2 ms 2652 KB Output is correct
32 Correct 2 ms 2648 KB Output is correct
33 Correct 2 ms 2852 KB Output is correct
34 Correct 3 ms 2652 KB Output is correct
35 Correct 42 ms 8472 KB Output is correct
36 Correct 57 ms 8904 KB Output is correct
37 Correct 58 ms 8644 KB Output is correct
38 Correct 45 ms 8904 KB Output is correct
39 Correct 53 ms 9668 KB Output is correct
40 Correct 160 ms 72900 KB Output is correct
41 Correct 113 ms 41160 KB Output is correct
42 Correct 111 ms 41924 KB Output is correct
43 Correct 137 ms 42432 KB Output is correct
44 Correct 138 ms 43204 KB Output is correct
45 Correct 56 ms 17100 KB Output is correct
46 Correct 49 ms 9564 KB Output is correct
47 Correct 69 ms 24256 KB Output is correct
48 Correct 97 ms 42176 KB Output is correct
49 Correct 56 ms 12260 KB Output is correct
50 Correct 114 ms 12484 KB Output is correct