제출 #557049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557049		Alexandruabcde	Long Distance Coach (JOI17_coach)	C++14	100 / 100	163 ms	28092 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 (a >= b) return;

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

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

    LL Best (int nod, int a, int b, int x) {
        LL val = Value(1LL * x, arb[nod]);
        int mij = (a + b) / 2;

        if (b - a == 1)
            return val;

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

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

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

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

int N, M;
LL X, 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 ) {
        LL 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 * 1LL * (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: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29