Submission #1189006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189006		12345678	Long Distance Coach (JOI17_coach)	C++20	71 / 100	2095 ms	8256 KiB

coach

#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], qs[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++)
    {
        qs[i]=qs[i-1]+d[i].second;
        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--)
            {
                dp[i]=min(dp[i], dp[j]+(i-j)*w*amt+qs[i]-qs[j]);
            }
        }
        //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
*/

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 0 / 29