Submission #890590

#	Time	Username	Problem	Language	Result	Execution time	Memory
890590		shivamxd	Knapsack (NOI18_knapsack)	C++17	73 / 100	1051 ms	6236 KiB

knapsack

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;


// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;


//PBDS (Policy_Based_Data_Structure)
/* 
   Note - To use it as ordered multiset, change less<int> to less_equal<int>. Note that doing this swaps 
   the functions of lower_bound and upper_bound. So upper_bound now works as lower_bound and vice versa.
   To erase an element, use oset.erase(oset.upper_bound(value));
*/
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 
// // find_by_order - oset.find_by_order(index) - returns element at that index
// order_of_key - oset.order_of_key(value) - return index of that element
 
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
 
// // #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_set tree<string, null_type,less_equal<string>, rb_tree_tag,tree_order_statistics_node_update>

  #define int long long
#define lld  double
using ll = long long;
// using __int128=long long;

 
const int mod=998244353,MAXN=33,INF=1<<30,N=2e5+10;
#define F first
#define S second
#define pb push_back
#define mpp make_pair
#define all(v) v.begin(),v.end()
#define add(x,y) (x+y)%mod
#define mul(x,y) (((x%mod)*(y%mod))%mod)
 
#define REP(i,a,b) for (int i = a; i <= b; i++)
 
 
#define nl "\n" 

 int MOD = 998244353;
const int TWO_MOD_INV = 500000004;
const ll maxn=5e3+10;



#define left(i) (2*i + 1)
#define right(i) (2*i + 2)
#define parent(i) ((i-1)/2)
#include <vector>
 
template<class T>
class SegmentTree
{
    public:
        //tree constructors.
        SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
        SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
        
        //query the range l to r, 0 based array indexing.
        T query(int l, int r);
        
        //update the element at index idx to val.
        void update(int idx, T val);
        ///TODO lazy propagation
    private:
        //represents the segment tree.
        T *tree;
    
        //builds the segment tree.
        void buildTree(std::vector<T> data);
        
        //size of the segment tree array.
        int segTreeSize;
    
        //extra nodes must be added to array to make its size a power of 2
        //this is the value to be filled for the those nodes.
        T valueForExtraNodes;
    
        //specifies how to combine child node results to form parent node result.
        T (*combine)(T obj1, T obj2);
    
        //used to calculate the size of array needed to store the tree.
        int calculateSize(int n);
    
        //helps to solve a range query.
        T queryHelper(int l,int r, int st, int ed, int node);
};
 
template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
                                                T value, T (*combine)(T obj1, T obj2))
{
   this->combine = combine;
   valueForExtraNodes = value;
   segTreeSize = calculateSize(data.size());
   buildTree(data);
}
 
template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
                                            T value, T (*combine)(T obj1, T obj2))
{
   this->combine = combine;
   valueForExtraNodes = value;
   segTreeSize = calculateSize(n);
 
   std::vector<T> data;
   for(int i = 0; i < n; i++)
         data.push_back(ar[i]);
 
   buildTree(data);
}
 
 
template<class T> int SegmentTree<T>::calculateSize(int n)
{
    int pow2 = 1;
    while( pow2 < n)
    {
        pow2 = pow2 << 1;
    }
    return 2*pow2 - 1;
}
 
template<class T> T SegmentTree<T>::query(int l, int r)
{
    int st = 0, ed = segTreeSize/2;
    return queryHelper(l, r, st, ed, 0);
}
 
template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
{
    if( (r < st) || (l > ed) || (l > r) )
        return valueForExtraNodes;
    if(st >= l && ed <= r)
        return tree[node];
    T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
    T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
    return combine(leftVal, rightVal);
}
 
template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
{
   int n = data.size();
   tree = new T[segTreeSize];
   int extraNodes = (segTreeSize/2 + 1) - n;
   for(int i = segTreeSize - 1; i >= 0; i--)
   {
       if(extraNodes>0)
           {
               tree[i] = valueForExtraNodes;
               extraNodes--;
           }
       else if(n>0)
           {
               tree[i] = data[n-1];
               n--;
           }
       else
           tree[i] = combine(tree[left(i)], tree[right(i)]);
   }
}
 
template<class T> void SegmentTree<T>::update(int idx, T val)
{
    int segTreeIdx = (segTreeSize/2) + idx;
    tree[segTreeIdx] = val;
    while(parent(segTreeIdx) >= 0)
    {
        segTreeIdx = parent(segTreeIdx);
        if(right(segTreeIdx) < segTreeSize)
          tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
        if(segTreeIdx == 0)
            break;
    }
}



//--------------------------------struct for overflow check-------------------------------------

// struct mi {
//     int v;
//     explicit operator int() const { return v; }
//     mi() { v = 0; }
//     mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
// };
// mi &operator+=(mi &a, mi b) {
//     if ((a.v += b.v) >= MOD) a.v -= MOD;
//     return a;
// }
// mi &operator-=(mi &a, mi b) {
//     if ((a.v -= b.v) < 0) a.v += MOD;
//     return a;
// }
// mi operator+(mi a, mi b) { return a += b; }
// mi operator-(mi a, mi b) { return a -= b; }
// mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); }
// mi &operator*=(mi &a, mi b) { return a = a * b; }
// mi pow(mi a, long long p) {
//     assert(p >= 0);
//     return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);
// }
// mi inv(mi a) {
//     assert(a.v != 0);
//     return pow(a, MOD - 2);
// }
// mi operator/(mi a, mi b) { return a * inv(b); }



//------------------------------------------------------


 
int inv(int i) {
  return i <= 1 ? i : mod - (int)(mod/i) * inv(mod % i) % mod;
}
 
long long binpow(long long a, long long b, long long m=mod) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
void usaco(){
    freopen("snakes.in", "r", stdin);   
    freopen("snakes.out", "w", stdout);
}
int minn(int a,int b){
    return min(a,b);
}



vector<int> v[N];
pair<int,int>dp[N];

void dfs(int par,int gpar){
    int sum=0;
    for(int child: v[par]){
        if(child!=gpar){
            dfs(child,par);
            sum+=dp[child].S;
        }
    }
    int minn=0;
    for(int child: v[par]){
        if(sum-dp[child].S<dp[child].F){
            minn=dp[child].F+dp[child].S-sum;
        }
    }
    if((sum-minn)%2!=0){
        minn++;
    }
    // cout<<par<<" "<<dp[par].F<<" "<<dp[par].S<<nl;
    dp[par]={minn+1,sum+1};
}



void solve(){
    int s,n;
    cin>>s>>n;
    int dp[s+1];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++){
        int v,w,k;
        cin>>v>>w>>k;
        k=min(k,s/w);
        for(int j=0;j<k;j++){
            for(int l=s;l>=w;l--){
                dp[l]=max(dp[l],v+dp[l-w]);

            }
        }
    }
    int ans=0;
    for(int i=0;i<=s;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans<<nl;
    
    







}



 
 
 
signed main(){
    


    
 
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t=1 ;
    // usaco();
    // cin>>t;
    
    
    
    
    while(t--){
        solve();
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'void usaco()':
knapsack.cpp:241:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |     freopen("snakes.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:242:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  242 |     freopen("snakes.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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