# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
883928 | 2023-12-06T12:17:15 Z | DAleksa | Long Distance Coach (JOI17_coach) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; long long X, T; int n, m, W; int a[N]; int b[N], B[N]; long long c[N], C[N]; int order[N]; long long pref[N]; long long dp[N]; int ind[N]; int cnt[N]; vector<long long> all; map<long long, int> start_to_index; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> X >> n >> m >> W >> T; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= m; i++) cin >> B[i] >> C[i]; for(int i = 1; i <= m; i++) order[i] = i; sort(order + 1, order + m + 1, [&](int i, int j) { return B[i] < B[j]; }); for(int i = 1; i <= m; i++) { b[i] = B[order[i]]; c[i] = C[order[i]]; all.push_back(b[i]); start_to_index[b[i]] = i; pref[i] = pref[i - 1] + c[i]; cnt[i] = X / T + (b[i] <= X % T); } sort(all.begin(), all.end()); for(int i = n; i >= 1; i--) { int lst = a[i - 1] % t, temp = a[i] % t; int index = lower_bound(all.begin(), all.end(), temp) - all.begin(); if(index == 0) index = all.size() - 1; else index--; if(a[i] - ((temp - all[index] + t) % t) < a[i - 1]) continue; ind[start_to_index[(a[i] - ((temp - all[index] + t) % t)) % t]] = a[i] - ((temp - all[index] + t) % t); } for(int i = 1; i <= n; i++) { dp[i] = dp[i - 1] + W * cnt[i]; dp[i] = min(dp[i], funkcija); } return 0; }