Submission #1188997

#TimeUsernameProblemLanguageResultExecution timeMemory
118899712345678Long Distance Coach (JOI17_coach)C++20
71 / 100
2092 ms7412 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const ll nx=2e5+5, inf=4e18; ll x, n, m, w, t, s[nx], dp[nx], mn[nx]; vector<pair<ll, ll>> d(nx); int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>x>>n>>m>>w>>t; for (int i=1; i<=n; i++) cin>>s[i]; s[++n]=x; sort(s+1, s+n+1); for (int i=1; i<=m; i++) cin>>d[i].first>>d[i].second, mn[i]=inf; sort(d.begin()+1, d.begin()+m+1); for (int i=1; i<=n; i++) { auto idx=lower_bound(d.begin()+1, d.begin()+m+1, make_pair(s[i]%t, 0ll))-d.begin()-1; mn[idx]=min(mn[idx], (ll)i); } dp[0]=w*(x/t+1); for (int i=1; i<=m; i++) { dp[i]=dp[i-1]+w*((x-d[i].first)/t+1); if (mn[i]!=inf) { ll sm=0, amt=(s[mn[i]]-d[i].first)/t; for (int j=i-1; j>=0; j--) { sm+=w*amt+d[j+1].second; dp[i]=min(dp[i], dp[j]+sm); } } //cout<<"debug "<<i<<' '<<dp[i]<<' '<<mn[i]<<'\n'; } cout<<dp[m]; } /* 0 1 2 4 6 7 8 9 11 13 14 15 16 18 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...