Submission #1095272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095272		I_am_Polish_Girl	Marathon Race 2 (JOI24_ho_t3)	C++14	81 / 100	167 ms	56596 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimization ("unroll-loops")

#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <bitset>
#include <cmath>

using namespace std;


int log_ = 3;
int inf = 2000000;
int mod = 1000000007;

int p = 501;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, x;
    cin >> n >> x;

    int m = n;

    vector <int> a(n);


    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a.begin(), a.end());

    vector <pair <int, int>> vp;

    vp.push_back({ a[0] , 1 });

    for (int i = 1; i < n; i++)
    {
        if (a[i - 1] == a[i])
        {
            vp[vp.size() - 1].second++;
        }
        else
        {
            vp.push_back({ a[i] , 1 });
        }
    }

    n = vp.size();

    if (n > 1000)
    {
        int q;
        cin >> q;

        while (q--)
        {
            cout << "No\n";
        }

        return 0;
    }

    vector <vector <vector <pair <int, int>>>> dp;

    dp.resize(n);

    for (int i = 0; i < n; i++)
    {
        dp[i].resize(n);

        for (int j = 0; j < n; j++)
        {
            dp[i][j].resize(2, { inf , inf });
        }
    }

    int c = 1;

    dp[0][n - 1][0] = { 0 , (vp[n - 1].first - vp[0].first) * c };
    dp[0][n - 1][1] = { (vp[n - 1].first - vp[0].first) * c  , 0};

    vector <int> pref(n);

    int p = 0;

    for (int i = 0; i < n; i++)
    {
        p += vp[i].second;

        pref[i] = p;
    }

    a.clear();

    for (int i = 0; i < n; i++)
    {
        a.push_back(vp[i].first);
    }


    for (int s = n - 2 ; s >= 0; s--)
    {
        
        for (int l = 0; l < n; l++)
        {
            int r = l + s;

            if (r >= n)
                continue;

            int c = pref[r];

            if (l > 0)
                c -= pref[l - 1];

            c = m - c + 1;

            for (int k = 0; k < 2; k++)
            {

                if (k == 0)
                {
                    if (l > 0)
                    {
                        dp[l][r][k].first = min(dp[l][r][k].first, dp[l - 1][r][0].first + c * (a[l] - a[l - 1]));
                        dp[l][r][k].second = min(dp[l][r][k].second, dp[l - 1][r][0].second + c * (a[l] - a[l - 1]));
                    }

                    if (r + 1 < n)
                    {
                        dp[l][r][k].first = min(dp[l][r][k].first, dp[l][r + 1][1].first + c * (a[r + 1] - a[l]));
                        dp[l][r][k].second = min(dp[l][r][k].second, dp[l][r + 1][1].second + c * (a[r + 1] - a[l]));
                    }
                }
                else
                {
                    if (l > 0)
                    {
                        dp[l][r][k].first = min(dp[l][r][k].first, dp[l - 1][r][0].first + c * (a[r] - a[l - 1]));
                        dp[l][r][k].second = min(dp[l][r][k].second, dp[l - 1][r][0].second + c * (a[r] - a[l - 1]));
                    }

                    if (r + 1 < n)
                    {
                        dp[l][r][k].first = min(dp[l][r][k].first, dp[l][r + 1][1].first + c * (a[r + 1] - a[r]));
                        dp[l][r][k].second = min(dp[l][r][k].second, dp[l][r + 1][1].second + c * (a[r + 1] - a[r]));
                    }
                }
            }
        }
    }

    

    int q;
    cin >> q;

    while (q--)
    {
        int st, fi, t_;

        cin >> st >> fi >> t_;

        int ind = n;

        pair <int, int> p = { fi , 1 };
        if (vp[n - 1].first >= fi)
            ind = lower_bound(vp.begin(), vp.end(), p) - vp.begin();

        int ans = inf;

        if (ind < n)
        {
            int a1 = dp[ind][ind][0].first;
            int a2 = dp[ind][ind][0].second;

            int ans1 = min(a1 + abs(a[0] - st), a2 + abs(a[n - 1] - st));

            ans1 += abs(a[ind] - fi) * (m+1);

            ans = min(ans, ans1);
        }

        ind--;

        if (ind >= 0)
        {
            int a1 = dp[ind][ind][0].first;
            int a2 = dp[ind][ind][0].second;

            int ans1 = min(a1 + abs(a[0] - st), a2 + abs(a[n - 1] - st));

            ans1 += abs(a[ind] - fi) * (m + 1);

            ans = min(ans, ans1);
        }

        ans += m;

        if (ans <= t_)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

Compilation message (stderr)

Main.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 19 / 19
• Subtask 7: 0 / 19