The problem is basically monopoly but you don't need to roll dices or stuffs, we have $N$ $(1 \leq N \leq 10^5)$ positions each of which are all empty. We can play any number of rounds by each rounds we choose an index $i$, if it's empty, we'll build a house on that position which will cost us $A_i$, and gives us 1 points, but if it's a house already, we'll transform the house to a apartment, which will cost us $B_i$, and gives us 1 points, if it's already an apartment we'll do nothing, which gives us nothing and cost us nothing (so there's no reason to do this). **We always want to maximize the amount of points.** (We can make an apartment on the position $i$ if and only if the position $i$ is a already a house)↵
↵
There will be $Q$ $(1 \leq Q \leq 10^5)$ queries, on the $ith$ query $(1 \leq i \leq Q)$ we have a budget of $X_i$, which means that the total sums of cost cannot exceed $X_i$. We want to know that, for each queries $i$ $(1 \leq i \leq Q)$ what is the maximum amount of points we can possibly get?↵
↵
Constraints:↵
↵
- $1 \leq N,Q \leq 10^5$↵
↵
- $1 \leq A_i,B_i \leq 10^{149}$↵
↵
- $1 \leq X_i \leq 2 \cdot 10^{14}$↵
↵
<spoiler summary="What I tried(Not the full solution)">↵
Time complexity: $O(N^2+QlogN)$↵
↵
I made a knapsack $ks$ as an array of size of $2 \cdot N$ , which $ks_i$ represent the minimum cost to get $i$ amount of points.(takes time of $O(N^2)$ of precomputing), then I received the queries and binary searched the maximum amount of points we can get and outputted it.(takes time of $O(QlogN)$) aaaand I'm stuck here. I don't know how to optimize this further...↵
↵
~~~~~↵
/********************↵
* what the sigma *↵
********************/↵
#include <iostream>↵
#include <vector>↵
#include <map>↵
#include <queue>↵
#include <algorithm>↵
#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>↵
using namespace std;↵
#define lgm cin.tie(0)->sync_with_stdio(0);↵
#define be(x) x.begin(),x.end()↵
#define ve vector↵
#define ll long long↵
#define ld long double↵
#define db(x) cout << "Debug at " << x << endl;↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define pii pair<int, int>↵
#define tii tuple<int,int,int>↵
#define pll pair<ll,ll>↵
#define sz(x) (int)x.size()↵
#define pb push_back↵
const int mod = 1e9+7,maxn=200005;↵
ll ks[200001];↵
int main() {↵
cin.tie(0)->sync_with_stdio(0);↵
ll n,cnt=0,cnt2=0;↵
cin >> n;↵
ll a[n],b[n];↵
vector<ll> v;↵
for (ll i=0;i<n;i++) {↵
cin >> a[i];↵
v.push_back(a[i]);↵
}↵
for (ll i=0;i<n;i++) {↵
cin >> b[i];↵
v.push_back(b[i]);↵
if (a[i] <= b[i]) {↵
cnt++;↵
} else if (a[i]>=b[i]) {↵
cnt2++;↵
}↵
}↵
ll q;↵
cin >> q;↵
ll m=100000;↵
m=m*m*m;↵
ll x;↵
for (int i=1;i<=2*n;i++) {↵
ks[i]=m;↵
}↵
for (int i=0;i<n;i++) {↵
for (int j=2*(i+1);j>=2;j--) {↵
ks[j]=min(ks[j],min(ks[j-1]+a[i],ks[j-2]+a[i]+b[i]));↵
}↵
ks[1]=min(a[i],ks[1]);↵
}↵
while (q--) {↵
cin >> x;↵
int l=upper_bound(ks,ks+2*n+1,x)-ks-1;↵
cout << l<<'\n';↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
I could not find a solution. But if anyone can, please comment what the solution to this problem could be(Other people would know too!), I would really appreciate it!↵
↵
Thanks in advance!
↵
There will be $Q$ $(1 \leq Q \leq 10^5)$ queries, on the $ith$ query $(1 \leq i \leq Q)$ we have a budget of $X_i$, which means that the total sums of cost cannot exceed $X_i$. We want to know that, for each queries $i$ $(1 \leq i \leq Q)$ what is the maximum amount of points we can possibly get?↵
↵
Constraints:↵
↵
- $1 \leq N,Q \leq 10^5$↵
↵
- $1 \leq A_i,B_i \leq 10^{
↵
- $1 \leq X_i \leq 2 \cdot 10^{14}$↵
↵
<spoiler summary="What I tried(Not the full solution)">↵
Time complexity: $O(N^2+QlogN)$↵
↵
I made a knapsack $ks$ as an array of size of $2 \cdot N$ , which $ks_i$ represent the minimum cost to get $i$ amount of points.(takes time of $O(N^2)$ of precomputing), then I received the queries and binary searched the maximum amount of points we can get and outputted it.(takes time of $O(QlogN)$) aaaand I'm stuck here. I don't know how to optimize this further...↵
↵
~~~~~↵
/********************↵
* what the sigma *↵
********************/↵
#include <iostream>↵
#include <vector>↵
#include <map>↵
#include <queue>↵
#include <algorithm>↵
#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>↵
using namespace std;↵
#define lgm cin.tie(0)->sync_with_stdio(0);↵
#define be(x) x.begin(),x.end()↵
#define ve vector↵
#define ll long long↵
#define ld long double↵
#define db(x) cout << "Debug at " << x << endl;↵
#define ull unsigned ll↵
#define f first↵
#define s second↵
#define pii pair<int, int>↵
#define tii tuple<int,int,int>↵
#define pll pair<ll,ll>↵
#define sz(x) (int)x.size()↵
#define pb push_back↵
const int mod = 1e9+7,maxn=200005;↵
ll ks[200001];↵
int main() {↵
cin.tie(0)->sync_with_stdio(0);↵
ll n,cnt=0,cnt2=0;↵
cin >> n;↵
ll a[n],b[n];↵
vector<ll> v;↵
for (ll i=0;i<n;i++) {↵
cin >> a[i];↵
v.push_back(a[i]);↵
}↵
for (ll i=0;i<n;i++) {↵
cin >> b[i];↵
v.push_back(b[i]);↵
if (a[i] <= b[i]) {↵
cnt++;↵
} else if (a[i]>=b[i]) {↵
cnt2++;↵
}↵
}↵
ll q;↵
cin >> q;↵
ll m=100000;↵
m=m*m*m;↵
ll x;↵
for (int i=1;i<=2*n;i++) {↵
ks[i]=m;↵
}↵
for (int i=0;i<n;i++) {↵
for (int j=2*(i+1);j>=2;j--) {↵
ks[j]=min(ks[j],min(ks[j-1]+a[i],ks[j-2]+a[i]+b[i]));↵
}↵
ks[1]=min(a[i],ks[1]);↵
}↵
while (q--) {↵
cin >> x;↵
int l=upper_bound(ks,ks+2*n+1,x)-ks-1;↵
cout << l<<'\n';↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
I could not find a solution. But if anyone can, please comment what the solution to this problem could be(Other people would know too!), I would really appreciate it!↵
↵
Thanks in advance!
