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();
}