Submission #1188989

#TimeUsernameProblemLanguageResultExecution timeMemory
118898912345678Long Distance Coach (JOI17_coach)C++20
71 / 100
2093 ms7112 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;
            for (int j=i-1; j>=0; j--)
            {
                sm+=w*((s[mn[i]]-d[j+1].first)/t)+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...