Blog entries - Codeforces

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^{9}$$$
$$$1 \leq X_i \leq 2 \cdot 10^{14}$$$

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';
    }
}

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!

Full text and comments »

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	jiangly	3631
4	Kevin114514	3574
5	maroonrk	3521
6	strapple	3515
7	Radewoosh	3461
8	tourist	3428
9	turmax	3378
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	140
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

SkyMagic's blog