Submission #557045

#	Time	Username	Problem	Language	Result	Execution time	Memory
557045		Alexandruabcde	Long Distance Coach (JOI17_coach)	C++14	0 / 100	1 ms	468 KiB

coach

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair <LL, LL> PLL;

constexpr LL INF = 1LL * 1e18;
constexpr int NMAX = 2e5 + 5;

LL Value (LL x, PLL line) {
    return line.first * x + line.second;
}

class LiChao {
private:
    vector <PLL> arb;
    int sz;

    void Update (int nod, int a, int b, PLL line) {
        if (arb[nod].first == INF && arb[nod].second == INF) {
            arb[nod] = line;
            return;
        }

        if (a == b) {
            if (Value(a, arb[nod]) > Value(a, line))
                arb[nod] = line;

            return;
        }

        int mij = (a + b) / 2;
        bool st = Value(a, arb[nod]) < Value(a, line);
        bool m = Value(mij+1, arb[nod]) < Value(mij+1, line);
        if (!m)
            swap(arb[nod], line);

        if (m != st) Update(2*nod, a, mij, line);
        else Update(2*nod+1, mij+1, b, line);
    }

    LL Best (int nod, int a, int b, int x) {
        if (arb[nod].first == INF && arb[nod].second == INF) return INF;

        LL val = arb[nod].first * x + arb[nod].second;
        int mij = (a + b) / 2;

        if (x <= mij) return min(val, Best(2*nod, a, mij, x));
        else return min(val, Best(2*nod+1, mij+1, b, x));
    }
public:
    void Init (int Size) {
        sz = Size;
        arb.resize(4*Size + 4);

        for (int i = 1; i <= 4 * sz; ++ i ) {
            arb[i] = {INF, INF};
        }
    }

    void AddLine (LL fr, LL sec) {
        Update(1, 1, sz, {fr, sec});
    }

    LL Answer (int ind) {
        return Best(1, 1, sz, ind);
    }
};

int X, N, M, W, T;

PLL refill[NMAX];
PLL pass[NMAX];

LL dp[NMAX];
LL spC[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> X >> N >> M >> W >> T;

    for (int i = 1; i <= N; ++ i ) {
        int s;
        cin >> s;

        refill[i].first = s % T;
        refill[i].second = s / T;
    }

    ++ N;
    refill[N].first = X % T;
    refill[N].second = X / T;

    for (int i = 1; i <= M; ++ i )
        cin >> pass[i].first >> pass[i].second;

    sort(refill + 1, refill + N + 1);
    sort(pass + 1, pass + M + 1);

    for (int i = 1; i <= M; ++ i )
        spC[i] = spC[i-1] + pass[i].second;
}

void Solve () {
    LiChao Tree;
    Tree.Init(M);

    int unused = N;
    for (int i = M; i >= 1; -- i ) {
        for (; unused >= 1; -- unused ) {
            if (pass[i].first >= refill[unused].first) break;

            LL m = - W * refill[unused].second;
            LL n = W * (i + 1) * refill[unused].second + spC[i] + dp[i+1];
            Tree.AddLine(m, n);
        }

        dp[i] = dp[i+1] + W * (X / T + (pass[i].first < X % T));

        dp[i] = min(dp[i], Tree.Answer(i) - spC[i-1]);
    }

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

int main () {
    Read();
    Solve();

    return 0;
}

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