CSES Problem Book Shops II Help Please

https://cses.fi/problemset/task/1159/

In this problem I used 0-1 knapsack to solve but got time limit exceeded. My approach to handle copies was to make duplicates of those items and apply knapsack. But it failed to pass few of the test cases(TLE). Any help will be appreciated.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define _READ freopen("input.txt", "r", stdin);
#define _FAST                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
int32_t main()
{
    _FAST
    int n,w;
    cin>>n>>w;
    vector<int> dp(w+1,0);
    //dp[weight]-->maximum price can have using 
    vector<int> h(n),s(n),k(n);
    for(auto &i:h)
        cin>>i;
    for(auto &i:s)
        cin>>i;
    for(auto &i:k)
        cin>>i;
    vector<pair<int,int>> v;//weight,price
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<k[i];j++)
        {
            v.push_back({h[i],s[i]});
        }
    }
    int m=v.size();
    for(int i=0;i<m;i++)
    {
        int price=v[i].S;
        int weight=v[i].F;
        for(int j=w;j-weight>=0;j--)
            dp[j]=max(dp[j],dp[j-weight]+price);
    }
    cout<<dp[w];
    return 0;
}
1 Like

Your approach is too slow. You can solve it in O(Nx + \sum price[i]).

Let’s define dp_{i,j} as the maximum number of pages possible from the first i type of books at a total price of j.

We can notice that
dp_{i,j} = max(dp_{i-1,j - k\times price[i]} + k \times pages[i]) \forall k\le maxbooks[i]

You can use a modification of the data structure used in the solution of BINLAND to quickly compute this value.

We will maintain price[i] queues. One for each possible value of j\mod price[i]. Each queue may not have more than maxbooks[i] elements.

Notice that the first value in the queue will add maxbooks[i] * pages[i] pages, and the last value will add only pages[i].

We can maintain this difference by maintaining a value \Delta, which we will add while returning the maximum. When we add a new value val = dp_{i,w}, we will subtract \Delta from val, and then add pages[i] to \Delta.

Rememeber the queue will maintain the last maxbooks[i] values in order.

Now the previous values will increase by pages[i] and this value is in the end and will add pages[i] Therefore maintaining the correct values. When popping, we don’t need to do anything, because the value adding more than maxbooks[i] \times pages[i] will get removed.

Solution
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
template<typename T>
ostream& operator+(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out<<x<<" ";
    }
    out<<"\n";
    return out;
}
template<typename T>
ostream& operator*(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out+x;
    }
    return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
    for(auto &x : vec){
        in>>x;
    }
    return in;
}
struct maxqueue{
    int pages;
    int currdelta;
    stack<pair<int,int>> stack1, stack2;
    maxqueue(int pages) : pages(pages), currdelta(0){}
    int getmax(){
        int ans = -1e9;
        if(!stack1.empty()){
            ans= max(ans, stack1.top().second + currdelta);
        }
        if(!stack2.empty()){
            ans = max(ans, stack2.top().second + currdelta);
        }
        return ans;
    }
    void push(int val){
        val-=currdelta;
        if(stack1.empty()){
            stack1.push(mp(val, val));
        }
        else{
            stack1.push(mp(val, max(val, stack1.top().second)));
        }
        currdelta+=pages;
    }
    void pop(){
        if(!stack2.empty()){
            stack2.pop();
            return;
        }
        assert(!stack1.empty());
        stack2.push(mp(stack1.top().first, stack1.top().first));
        stack1.pop();
        while(!stack1.empty()){
            stack2.push(mp(stack1.top().first, max(stack1.top().first, stack2.top().second)));
            stack1.pop();
        }
        stack2.pop();
    }
    int size(){
        return stack1.size() + stack2.size();
    }
};
void solve(){
    int n,x;
    cin>>n>>x;
    vector<int> price(n), maxbooks(n), pages(n);
    cin>>price>>pages>>maxbooks;
    int dp[n+1][x+1];
    for(int i=0;i<=x;i++){
        dp[0][i]=0;
    }
    for(int i=0;i<n;i++){
        vector<maxqueue> val(price[i], maxqueue(pages[i]));
        for(int w = 0;w<=x;w++){
            dp[i+1][w] = max(dp[i][w], val[w%price[i]].getmax());
            val[w%price[i]].push(dp[i][w]);
            if(val[w%price[i]].size() > maxbooks[i]){
                val[w%price[i]].pop();
            }
        }
    } 
    int ans = 0;
    for(int i=0;i<=x;i++){
        ans = max(ans, dp[n][i]);
    }
    cout<<ans<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}