Submission #1239109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239109		sunnat	Marathon Race 2 (JOI24_ho_t3)	C++20	24 / 100	1 ms	840 KiB

Main

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;
#define int long long
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, l, q;
    cin >> n >> l;
    map<int, int> mp;
    for(int i = 0, x; i < n; ++ i){
        cin >> x;
        ++mp[x];
    }
    vector<pair<int, int> > a(mp.begin(), mp.end());
    
    for(int i = 1; i < a.size(); ++ i)
        a[i].second += a[i-1].second;
    int mn1 = 0, mn2 = 0, mn;
    for(int i = 1; i < a.size(); ++ i){
        mn1 += (a[i].first - a[i-1].first) * (a[i-1].second + 1);
        mn2 += (a[a.size() - i].first - a[a.size() - i - 1].first) * (n - a[a.size() - i - 1].second + 1);
    }
    mn = min(mn1, mn2);
    vector dp(4, vector(a.size(), vector(a.size(), 1000000000LL)));
    
    
    int m = a.size();
    if(mn <= 5e5){
        dp[0][0][m-1] = 0;
        dp[1][0][m-1] = a.back().first - a.front().first;
        dp[2][0][m-1] = a.back().first - a.front().first;
        dp[3][0][m-1] = 0;
        for(int L = 0; L < m; ++ L){
            for(int R = m - 1; R >= L; -- R){
                if(L == 0 && R == m - 1) continue;
                int col = n - (a[R].second - (L == 0 ? 0LL : a[L-1].second));
                if(L != 0){
                    dp[0][L][R] = min(dp[0][L][R], dp[0][L-1][R] + (col+1)*(a[L].first - a[L-1].first));
                    dp[1][L][R] = min(dp[1][L][R], dp[0][L-1][R] + (col+1)*(a[R].first - a[L-1].first));
                    dp[2][L][R] = min(dp[2][L][R], dp[2][L-1][R] + (col+1)*(a[L].first - a[L-1].first));
                    dp[3][L][R] = min(dp[3][L][R], dp[2][L-1][R] + (col+1)*(a[R].first - a[L-1].first));
                }
                if(R != m-1){
                    dp[0][L][R] = min(dp[0][L][R], dp[1][L][R+1] + (col+1)*(a[R+1].first - a[L].first));
                    dp[1][L][R] = min(dp[1][L][R], dp[1][L][R+1] + (col+1)*(a[R+1].first - a[R].first));
                    dp[2][L][R] = min(dp[2][L][R], dp[3][L][R+1] + (col+1)*(a[R+1].first - a[L].first));
                    dp[3][L][R] = min(dp[3][L][R], dp[3][L][R+1] + (col+1)*(a[R+1].first - a[R].first));
                }
            }
        }
    }
    
    
    cin >> q;
    for(int i = 0, s, f, k, sol, id; i < q; ++ i){
        cin >> s >> f >> k;
        k -= n;
        if(mn > k){
            cout << "No\n";
        }
        else{
            sol = 1e9;
            id = lower_bound(a.begin(), a.end(), make_pair(f, 0LL)) - a.begin();
            if(id != a.size()){
                sol = min(sol, abs(s-a.front().first) + dp[0][id][id] + (n+1)*abs(a[id].first - f));
                sol = min(sol, abs(s-a.back().first) + dp[2][id][id] + (n+1)*abs(a[id].first - f));
            }
            id --;
            if(id != -1){
                sol = min(sol, abs(s-a.front().first) + dp[0][id][id] + (n+1)*abs(a[id].first - f));
                sol = min(sol, abs(s-a.back().first) + dp[2][id][id] + (n+1)*abs(a[id].first - f));
            }
            cout << (sol <= k ? "Yes\n" : "No\n");
        }
    }
    return 0;
}

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