Submission #1095144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095144		I_am_Polish_Girl	Marathon Race 2 (JOI24_ho_t3)	C++14	62 / 100	1559 ms	219712 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 <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);
        }
    }


    int q;
    cin >> q;

    while (q--)
    {
        int s, t , times;
        cin >> s >> t >> times;

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

        int c = n + 1;

        

        int ind = n;
        
        if (a[n - 1] >= t)
            ind = lower_bound(a.begin(), a.end(), t) - a.begin();

        if (ind < n)
            dp[ind][ind][1] = (n + 1) * abs(a[ind] - t);

        ind--;

        if (ind >= 0)
            dp[ind][ind][1] = (n + 1) * abs(a[ind] - t);

        for (int s = 0; s < n; 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 (l > 0)
                    {
                        if (k == 0)
                            dp[l - 1][r][0] = min(dp[l - 1][r][0], (dp[l][r][k] + abs(a[l] - a[l - 1]) * c));
                        else
                            dp[l - 1][r][0] = min(dp[l - 1][r][0], (dp[l][r][k] + abs(a[r] - a[l - 1]) * c));
                    }

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

                    }
                    
                }

            }
        }

        int ans1 = dp[0][n - 1][0] + abs(a[0] - s);
        int ans2 = dp[0][n - 1][1] + abs(a[n - 1] - s);

        int ans = min(ans1, ans2) + n;

        if (ans <= times)
            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: 0 / 19
• Subtask 7: 0 / 19