Submission #1294085

#TimeUsernameProblemLanguageResultExecution timeMemory
1294085nguyenkhangninh99Marathon Race 2 (JOI24_ho_t3)C++20
62 / 100
1597 ms31908 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, l; cin >> n >> l;
    
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    int q; cin >> q;
    while(q--){
        int s, g, t; cin >> s >> g >> t;
        
        vector<vector<int>> dp(n, vector<int>(n, 1e18));
        for(int i = 0; i < n; i++) dp[i][i] = abs(g - a[i]) * (n + 1);

        for(int len = 2; len <= n; len++){
            for(int i = 0; i + len - 1 < n; i++){
                int j = i + len - 1, w = n - len + 2;

                dp[i][j] = min(dp[i][j], dp[i + 1][j] + (a[i + 1] - a[i]) * w);
                dp[i][j] = min(dp[i][j], dp[j][i + 1] + (a[j] - a[i]) * w);

                dp[j][i] = min(dp[j][i], dp[j - 1][i] + (a[j] - a[j - 1]) * w);
                dp[j][i] = min(dp[j][i], dp[i][j - 1] + (a[j] - a[i]) * w);
            }
        }
        int res = min(dp[0][n - 1] + abs(s - a[0]), dp[n - 1][0] + abs(s - a[n - 1])) + n;
        cout << (res <= t ? "Yes" : "No") << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...