Submission #1057431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057431		sammyuri	Marathon Race 2 (JOI24_ho_t3)	C++17	7 / 100	1 ms	348 KiB

Main

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

typedef long long ll;

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());
    vector<ll> cost_forwards(n), cost_backwards(n);
    for (int i = 0; i < n; i ++) {
        // take i balls from prefix, n - i from suffix
        ll cost = 0;
        for (int j = 0; j < i - 1; j ++) {
            cost += abs(balls[j + 1] - balls[j]) * (j + 2);
        }
        cost += abs(balls[n - 1] - balls[max(0, i - 1)]) * (ll)(i + 1);
        ll cur = i + 1;
        for (int j = n - 1; j > i; j --) {
            cur ++;
            cost += (ll)abs(balls[j] - balls[j - 1]) * cur;
        }
        cost_forwards[i] = cost;
    }
    for (int i = 0; i < n; i ++) {
        // take i balls from suffix, n - i from prefix
        ll cost = 0;
        ll cur = 1;
        for (int j = n - 1; j > n - i; j --) {
            cur ++;
            cost += abs(balls[j] - balls[j - 1]) * cur;
        }
        if (i != 0)
            cur ++;
        cost += abs(balls[n - max(i, 1)] - balls[0]) * cur;
        for (int j = 0; j < n - i - 1; j ++) {
            cur ++;
            cost += (ll)abs(balls[j + 1] - balls[j]) * cur;
        }
        cost_backwards[i] = cost;
    }
    // for (int i = 0; i < n; i ++)
    //     cout << cost_forwards[i] << " " << cost_backwards[i] << endl;

    int q; cin >> q;
    while (q --) {
        int s, g, t; cin >> s >> g >> t;
        t -= n;
        ll best = 1e18;
        // try forwards first
        for (int i = 0; i < n; i ++)
            best = min(best, (ll)abs(s - balls[0]) + (ll)(n + 1)*abs(g - balls[i]) + cost_forwards[i]);
        // now backwards
        for (int i = 0; i < n; i ++)
            best = min(best, (ll)abs(s - balls[n - 1]) + (ll)(n + 1)*abs(g - balls[n - 1 - i]) + cost_backwards[i]);
        if (best <= t)
            cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

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