제출 #1239113

#제출 시각아이디문제언어결과실행 시간메모리
1239113sunnatMarathon Race 2 (JOI24_ho_t3)C++20
100 / 100
408 ms41088 KiB
#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]; } cin >> q; vector<pair<int, int> > a(mp.begin(), mp.end()); if(a.size() > 1000){ for(int i = 0; i < q; ++ i) cout << "No\n"; return 0; } for(int i = 1; i < a.size(); ++ i) a[i].second += a[i-1].second; vector dp(4, vector(a.size(), vector(a.size(), 1000000000LL))); int m = a.size(); 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)); } } } for(int i = 0, s, f, k, sol, id; i < q; ++ i){ cin >> s >> f >> k; k -= n; 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; }
#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...