Submission #1057440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057440		sammyuri	Marathon Race 2 (JOI24_ho_t3)	C++17	62 / 100	1555 ms	63068 KiB

Main

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

typedef long long ll;

const int MAXN = 2005;
const ll INF = 1e18;
ll dp[MAXN][MAXN][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] be minimum cost to collect balls i-j and then go to the end
    // starting from left if k = 0, right if k = 1
    // clearly the transitions are O(1)
    int q; cin >> q;
    while (q --) {
        int s, g, t; cin >> s >> g >> t;
        t -= n;
        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;
        for (int i = 0; i < n; i ++) {
            dp[i][i][0] = dp[i][i][1] = (ll)abs(balls[i] - g) * (ll)(n + 1);
        }
        for (int width = 1; width < n; width ++) {
            for (int i = 0; i < n - width; i ++) {
                int j = i + width;
                ll carrying = n + 1 - width;
                dp[i][j][0] = min(dp[i][j][0], dp[i + 1][j][0] + (ll)abs(balls[i + 1] - balls[i]) * carrying);
                dp[i][j][0] = min(dp[i][j][0], dp[i + 1][j][1] + (ll)abs(balls[j] - balls[i]) * carrying);
                dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][0] + (ll)abs(balls[j] - balls[i]) * carrying);
                dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + (ll)abs(balls[j] - balls[j - 1]) * carrying);
            }
        }
        ll best = min(dp[0][n - 1][0] + abs(balls[0] - s), dp[0][n - 1][1] + abs(balls[n - 1] - s));
        // cout << best << " " << dp[0][n - 2][1] << 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: 0 / 19
• Subtask 7: 0 / 19