I spent 10-15 mins trying to solve C thinking it was $$$n \leq 10^6$$$

Implement what's written in the problem statement.

Implement what's written in the problem statement.

Bruteforce the number of dishes of one of the types.

Calculate for each road the sum of the lengths of the paths $$$(X_k, X_{k + 1})$$$ that will pass through the current road (instead of the other arc of the circle), and the same for the ones that won't pass through the current road. This can be done with prefix sums. After that, try all the roads and calculate the length of the tour using the precalculated values.

For each chord $$$i$$$, check if there is another chord $$$j$$$ satisfying $$$A_i < A_j < B_i < B_j$$$ or $$$A_j < A_i < B_j < B_i$$$. This can be done using a data structure that supports range minimum/maximum queries.

If a walk exists, eventually, all the cities must be visited, in some order. Find an optimal order in which the cities will be visited using bitmask dynamic programming.

The answer to the problem is the minimum of the values $$$dp[2^n - 1][i] + dist[i][j]$$$ over all the valid pairs $$$i, j$$$. $$$dist[i][j]$$$ can be calculated for all pairs $$$i, j$$$ using Floyd–Warshall algorithm.

For each $$$i$$$, calculate two values:

• $$$dp_+[i]$$$ the sum of the evaluations of the subarrays starting at $$$i$$$.

• $$$dp_*[i]$$$ the sum of the evaluations of the subarrays starting at $$$i$$$ but not containing a '+' character.

The above values can be calculated from the right to the left by maintaining the positions of the last '+' and '*' characters and doing some casework.

The answer to the problem is the sum of all the values $$$dp_+[i]$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> q(n);
        vector<int> a(n);
        vector<int> b(n);
        for (int i = 0; i < n; i++)
            cin >> q[i];
        for (int i = 0; i < n; i++)
            cin >> a[i];
        for (int i = 0; i < n; i++)
            cin >> b[i];
        int l = 0;
        int r = 1e6 + 5;
        while (l < r)
        {
            bool ok = true;
            int mid = (l + r) / 2;
            for (int i = 0; i < n; i++)
            {
                if (b[i] > q[i] - (a[i] * mid))
                    ok = false;
            }
            if (ok)
                l = mid + 1;
            else
                r = mid;
        }
        int k = INT_MAX;
        for (int i = 0; i < n; i++)
        {
            if (b[i] == 0)
                continue;
            k = min(k, (q[i] - (a[i] * l)) / b[i]);
        }
        cout << l+k << "\n";
    }
}

#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<queue>

#define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define print(a) for (auto &x : a)cout<<x<<" ";
#define f(i, a, b) for (int i = a; i < b; i++)
#define printv(a,n) f(i,0,n) cout<<a[i]<<" ";

using namespace std;
using vi = vector<int>;
int Bit(int mask, int b) { return (mask >> b) & 1; }

const int infl = 1e6+3;
int n,qsum,asum,bsum;
vector<int>q,a,b;

bool ok(int mid ,int alim, int blim) {
    int adish = min(alim,mid), bdish = min(max(mid-alim,0ll),blim);

    if(mid>(adish+bdish)) {
        return false;
    }
    for(int i = 1;i<=mid+1;i++) {
        int total = (asum*adish+bsum*bdish);
        // cout<<adish<<" "<<bdish<<" "<<mid<<" "<<total<<" "<<qsum<<endl;

        if(total<=qsum and (adish+bdish)==mid) {
            return true;
        }
        adish = max(adish-1,0ll);
        bdish = min(bdish+1,blim);
    }
    return false;
}
void solve() {
    cin>>n;

    a = vector<int>(n);
    b = vector<int>(n);
    q = vector<int>(n);

    for(int i  = 0;i<n;i++) {
        cin>>q[i];
        qsum+=q[i];
    }

    asum = 0,bsum= 0;
    for(int i = 0;i<n;i++) {
        cin>>a[i];
        asum+=a[i];
    }

    for(int i = 0;i<n;i++) {
        cin>>b[i];
        bsum+=b[i];
    }

    int alim = infl, blim = infl;

    for(int i = 0;i<n;i++) {
        if(a[i]) {
            alim = min(alim,q[i]/a[i]);
        }
        if(b[i]) {
            blim = min(blim,q[i]/b[i]);
        }
    }

    int lo = 0, hi = (alim+blim),ans = 0;

    while(lo<=hi) {
        int mid = (lo+hi)>>1;
        if(ok(mid,alim,blim)) {
            ans = mid;
            lo = mid+1;
        }
        else {
            hi = mid-1;
        }
    }
    cout<<ans<<endl;
}

signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    for(int i = 1;i<=t;i++) {
        solve();
    }
}