Submission #1057562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057562		sammyuri	Marathon Race 2 (JOI24_ho_t3)	C++17	81 / 100	748 ms	259668 KiB

Main

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

typedef long long ll;

const int MAXN = 2005;
const int MAXL = 5e5 + 5;
const ll INF = 1e18;
ll dp[MAXN][MAXN][2][2];
ll dp2[MAXN][2];
ll cost[MAXL][2];

int main() {
    int n; cin >> n;
    int l; cin >> l;
    vector<int> balls(n);
    for (auto &a : balls) cin >> a;
    sort(balls.begin(), balls.end());
    // let dp[i][j][k][l] be minimum cost to collect balls i-j and then go to the end
    // starting from left if k = 0, right if k = 1
    // currently on left if l = 0, right if l = 1
    // clearly the transitions are O(1)
    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][0] = dp[i][j][k][1] = INF;
    dp[0][n - 1][0][0] = dp[0][n - 1][1][1] = 0;
    for (int width = n - 1; width > 0; width --) {
        for (int i = 0; i < n - width; i ++) {
            int j = i + width;
            ll carrying = n + 1 - width;
            for (int k = 0; k < 2; k ++) {
                dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][0] + (ll)abs(balls[i + 1] - balls[i]) * carrying);
                dp[i + 1][j][k][1] = min(dp[i + 1][j][k][1], dp[i][j][k][0] + (ll)abs(balls[j] - balls[i]) * carrying);
                dp[i][j - 1][k][0] = min(dp[i][j - 1][k][0], dp[i][j][k][1] + (ll)abs(balls[j] - balls[i]) * carrying);
                dp[i][j - 1][k][1] = min(dp[i][j - 1][k][1], dp[i][j][k][1] + (ll)abs(balls[j] - balls[j - 1]) * carrying);
            }
        }
    }
    for (int i = 0; i < n; i ++)
        for (int k = 0; k < 2; k ++)
            dp2[i][k] = min(dp[i][i][k][0], dp[i][i][k][1]);
    // now calculate best for each position
    int pp = 0;
    for (int i = 0; i <= l; i ++) {
        cost[i][0] = cost[i][1] = INF;
        while (pp < n && balls[pp] < i)
            pp ++;
        if (pp < n && balls[pp] == i)
            cost[i][0] = dp2[pp][0], cost[i][1] = dp2[pp][1];
        while (pp < n && balls[pp] == i)
            pp ++;
        if (pp > 0) {
            cost[i][0] = min(cost[i][0], (ll)abs(balls[pp - 1] - i) * (n + 1) + dp2[pp - 1][0]);
            cost[i][1] = min(cost[i][1], (ll)abs(balls[pp - 1] - i) * (n + 1) + dp2[pp - 1][1]);
        }
        if (pp < n) {
            cost[i][0] = min(cost[i][0], (ll)abs(balls[pp] - i) * (n + 1) + dp2[pp][0]);
            cost[i][1] = min(cost[i][1], (ll)abs(balls[pp] - i) * (n + 1) + dp2[pp][1]);
        }
    }
    
    int q; cin >> q;
    while (q --) {
        int s, g, t; cin >> s >> g >> t;
        t -= n;
        ll best = min(cost[g][0] + abs(balls[0] - s), cost[g][1] + abs(balls[n - 1] - s));
        // cout << best  << endl;
        if (best <= t)
            cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

• 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