Submission #1095247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095247		I_am_Polish_Girl	Marathon Race 2 (JOI24_ho_t3)	C++14	81 / 100	803 ms	1048576 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;

    vector <int> a(n);


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

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

    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 , (a[n - 1] - a[0]) * c };
    dp[0][n - 1][1] = { (a[n - 1] - a[0]) * c  , 0};

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

            if (r >= n)
                continue;

            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;

        if (a[n - 1] >= fi)
            ind = lower_bound(a.begin(), a.end(), fi) - a.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) * (n+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) * (n + 1);

            ans = min(ans, ans1);
        }

        ans += n;

        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