Submission #44787

#	Time	Username	Problem	Language	Result	Execution time	Memory
44787		choikiwon	Long Distance Coach (JOI17_coach)	C++17	100 / 100	258 ms	171392 KiB

coach

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double lf;
typedef pair<ll, ll> pll;

const int MN = 200010;

struct CHT {
    vector<ll> M, B;
    void init() {
        M.clear();
        B.clear();
    }
    bool bad(int l1, int l2, int l3) {
        return (lf)(B[l3] - B[l1]) / (M[l1] - M[l3]) <= (lf)(B[l2] - B[l1]) / (M[l1] - M[l2]) + 1e-12;
    }
    void add(ll m, ll b) {
        M.push_back(m);
        B.push_back(b);
        while(M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
            M.erase(M.end() - 2);
            B.erase(B.end() - 2);
        }
        if(M.size() == 2 && M[0] == M[1]) {
            M.erase(M.end() - 2);
            B.erase(B.end() - 2);
        }
    }
    ll query(ll x) {
        int s = 0, e = (int)M.size() - 2, p = 0;
        while(s <= e) {
            int m = (s + e)>>1;

            if((M[m] - M[m + 1]) * x >= (B[m + 1] - B[m])) {
                p = m + 1;
                s = m + 1;
            }
            else e = m - 1;
        }
        return M[p] * x + B[p];
    }
} cht;

ll X, T;
int N, M, W;
ll S[MN], Q[MN], C[MN], psum[MN], csum[MN], dp[MN], sum;
pll P[MN];
int chk[MN];

int main() {
    scanf("%lld %d %d %d %lld", &X, &N, &M, &W, &T);

    for(int i = 0; i < N; i++) {
        scanf("%lld", &S[i]);
    }
    for(int i = 0; i < M; i++) {
        scanf("%lld %lld", &P[i].first, &P[i].second);
    }

    S[N++] = X;
    sort(S, S + N);
    sort(P, P + M);

    sum += X / T + 1;
    for(int i = 0; i < M; i++) {
        C[i] = X / T + (P[i].first < X % T? 1 : 0);
        sum += C[i];
    }
    sum *= W;

    for(int i = 0; i < M; i++) {
        psum[i] = P[i].second;
        if(i) psum[i] += psum[i - 1];
    }
    for(int i = 0; i < M; i++) {
        csum[i] = C[i];
        if(i) csum[i] += csum[i - 1];
    }

    memset(Q, -1, sizeof(Q));
    for(int i = 0; i < N; i++) {
        int s = 0, e = M - 1, p = -1;
        while(s <= e) {
            int m = (s + e)>>1;

            if(P[m].first < S[i] % T) {
                p = m;
                s = m + 1;
            }
            else e = m - 1;
        }
        if(p != -1 && !chk[p]) {
            chk[p] = 1;
            Q[p] = S[i] / T;
        }
    }

    cht.init();
    for(int i = 0; i < M; i++) {
        dp[i] = i? dp[i - 1] : 0;

        cht.add(-1LL * W * i, (i? -psum[i - 1] : 0) + (i? -dp[i - 1] : 0) + (i? csum[i - 1] * W : 0));
        if(Q[i] != -1) {
            dp[i] = max(dp[i], -cht.query(Q[i]) - Q[i] * W * (i + 1) - psum[i] + csum[i] * W);
        }
    }

    printf("%lld", sum - dp[M - 1]);
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %d %d %d %lld", &X, &N, &M, &W, &T);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &S[i]);
         ~~~~~^~~~~~~~~~~~~~~
coach.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &P[i].first, &P[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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