Submission #211250

#	Time	Username	Problem	Language	Result	Execution time	Memory
211250		Alexa2001	Long Distance Coach (JOI17_coach)	C++17	100 / 100	197 ms	18476 KiB

coach

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf = 1e19;

const int Nmax = 2e5 + 5;
const ll eps = 1e-6;

int n, m, T, W, nr;
ll S[Nmax], P[Nmax];
int st[Nmax];

ll sumC[Nmax], need[Nmax], C[Nmax], dp[Nmax], sep[Nmax], coef[Nmax];
ll X;


void read()
{
    cin >> X >> n >> m >> W >> T;

    int i;
    for(i=1; i<=n; ++i) cin >> S[i];

    vector<pair<ll,int>> a(m+1);
    for(i=1; i<=m; ++i) cin >> a[i].first >> a[i].second;

    sort(a.begin() + 1, a.end());
    for(i=1; i<=m; ++i)
        P[i] = a[i].first, C[i] = a[i].second;
}

void prec()
{
    int i;
    for(i=1; i<=m; ++i)
    {
        sumC[i] = sumC[i-1] + C[i];
        need[i] = (X - P[i]) / T + 1;
    }

    for(i=1; i<=m; ++i) sep[i] = inf;

    S[++n] = X;
    for(i=1; i<=n; ++i)
    {
        int pos = lower_bound(P+1, P+m+1, S[i] % T) - P - 1;
        if(pos)
            sep[pos] = min<ll>(sep[pos], S[i] / T);
    }
}


namespace H
{
    static ll a[Nmax], b[Nmax];
    int nr = 0;

    long double meet(int x, int y)
    {
        return (long double) (b[x] - b[y]) / (a[y] - a[x]);
    }

    bool bad(int x, int y, int z)
    {
        return meet(x, y) - meet(y, z) < -eps;
    }

    void add(ll A, ll B)
    {
        a[0] = A; b[0] = B;
        while(nr >= 2 && bad(nr - 1, nr, 0)) --nr;
        a[++nr] = A; b[nr] = B;
        a[0] = b[0] = 0;
    }

    ll query(ll x)
    {
        int st = 1, dr = nr-1, mid;

        while(st <= dr)
        {
            mid = (st + dr) / 2;
            if(meet(mid, mid+1) - x > eps) st = mid + 1;
                else dr = mid - 1;
        }

        return a[st] * x + b[st];
    }
};

void solve()
{
    int i;

    H :: add(0, 0);

    for(i=1; i<=m; ++i)
    {
        dp[i] = dp[i-1] + need[i] * W;

        if(sep[i] != inf)
            dp[i] = min( dp[i], H :: query(-sep[i] * W) + sep[i] * i * W + sumC[i] );

        H :: add(i, dp[i] - sumC[i]);
    }

    cout << dp[m] + W * (X / T + 1) << '\n';
}

int main()
{
  //  freopen("input", "r", stdin);
   // freopen("output", "w", stdout);
    cin.sync_with_stdio(false); cin.tie(0);

    read();
    prec();
    solve();

    return 0;
}

Compilation message (stderr)

coach.cpp:6:16: warning: overflow in implicit constant conversion [-Woverflow]
 const ll inf = 1e19;
                ^~~~

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