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 \lt A_j \lt B_i \lt B_j$$$ or $$$A_j \lt A_i \lt B_j \lt 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";
    }
}