답안 #44787 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44787	2018-04-06T12:33:32 Z	choikiwon	Long Distance Coach (JOI17_coach)	C++17	100 / 100	258 ms	171392 KB

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

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.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1912 KB	Output is correct
2	Correct	3 ms	1912 KB	Output is correct
3	Correct	3 ms	1952 KB	Output is correct
4	Correct	3 ms	2008 KB	Output is correct
5	Correct	3 ms	2012 KB	Output is correct
6	Correct	3 ms	2020 KB	Output is correct
7	Correct	3 ms	2072 KB	Output is correct
8	Correct	3 ms	2112 KB	Output is correct
9	Correct	3 ms	2132 KB	Output is correct
10	Correct	3 ms	2136 KB	Output is correct
11	Correct	3 ms	2196 KB	Output is correct
12	Correct	3 ms	2196 KB	Output is correct
13	Correct	3 ms	2196 KB	Output is correct
14	Correct	3 ms	2340 KB	Output is correct
15	Correct	3 ms	2340 KB	Output is correct
16	Correct	4 ms	2340 KB	Output is correct
17	Correct	4 ms	2340 KB	Output is correct
18	Correct	4 ms	2340 KB	Output is correct
19	Correct	3 ms	2340 KB	Output is correct
20	Correct	3 ms	2348 KB	Output is correct
21	Correct	3 ms	2348 KB	Output is correct
22	Correct	3 ms	2348 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1912 KB	Output is correct
2	Correct	3 ms	1912 KB	Output is correct
3	Correct	3 ms	1952 KB	Output is correct
4	Correct	3 ms	2008 KB	Output is correct
5	Correct	3 ms	2012 KB	Output is correct
6	Correct	3 ms	2020 KB	Output is correct
7	Correct	3 ms	2072 KB	Output is correct
8	Correct	3 ms	2112 KB	Output is correct
9	Correct	3 ms	2132 KB	Output is correct
10	Correct	3 ms	2136 KB	Output is correct
11	Correct	3 ms	2196 KB	Output is correct
12	Correct	3 ms	2196 KB	Output is correct
13	Correct	3 ms	2196 KB	Output is correct
14	Correct	3 ms	2340 KB	Output is correct
15	Correct	3 ms	2340 KB	Output is correct
16	Correct	4 ms	2340 KB	Output is correct
17	Correct	4 ms	2340 KB	Output is correct
18	Correct	4 ms	2340 KB	Output is correct
19	Correct	3 ms	2340 KB	Output is correct
20	Correct	3 ms	2348 KB	Output is correct
21	Correct	3 ms	2348 KB	Output is correct
22	Correct	3 ms	2348 KB	Output is correct
23	Correct	3 ms	2348 KB	Output is correct
24	Correct	3 ms	2348 KB	Output is correct
25	Correct	3 ms	2348 KB	Output is correct
26	Correct	3 ms	2348 KB	Output is correct
27	Correct	3 ms	2348 KB	Output is correct
28	Correct	3 ms	2348 KB	Output is correct
29	Correct	4 ms	2348 KB	Output is correct
30	Correct	3 ms	2348 KB	Output is correct
31	Correct	4 ms	2348 KB	Output is correct
32	Correct	4 ms	2348 KB	Output is correct
33	Correct	4 ms	2348 KB	Output is correct
34	Correct	3 ms	2348 KB	Output is correct
35	Correct	4 ms	2348 KB	Output is correct
36	Correct	4 ms	2356 KB	Output is correct
37	Correct	4 ms	2360 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1912 KB	Output is correct
2	Correct	3 ms	1912 KB	Output is correct
3	Correct	3 ms	1952 KB	Output is correct
4	Correct	3 ms	2008 KB	Output is correct
5	Correct	3 ms	2012 KB	Output is correct
6	Correct	3 ms	2020 KB	Output is correct
7	Correct	3 ms	2072 KB	Output is correct
8	Correct	3 ms	2112 KB	Output is correct
9	Correct	3 ms	2132 KB	Output is correct
10	Correct	3 ms	2136 KB	Output is correct
11	Correct	3 ms	2196 KB	Output is correct
12	Correct	3 ms	2196 KB	Output is correct
13	Correct	3 ms	2196 KB	Output is correct
14	Correct	3 ms	2340 KB	Output is correct
15	Correct	3 ms	2340 KB	Output is correct
16	Correct	4 ms	2340 KB	Output is correct
17	Correct	4 ms	2340 KB	Output is correct
18	Correct	4 ms	2340 KB	Output is correct
19	Correct	3 ms	2340 KB	Output is correct
20	Correct	3 ms	2348 KB	Output is correct
21	Correct	3 ms	2348 KB	Output is correct
22	Correct	3 ms	2348 KB	Output is correct
23	Correct	3 ms	2348 KB	Output is correct
24	Correct	3 ms	2348 KB	Output is correct
25	Correct	3 ms	2348 KB	Output is correct
26	Correct	3 ms	2348 KB	Output is correct
27	Correct	3 ms	2348 KB	Output is correct
28	Correct	3 ms	2348 KB	Output is correct
29	Correct	4 ms	2348 KB	Output is correct
30	Correct	3 ms	2348 KB	Output is correct
31	Correct	4 ms	2348 KB	Output is correct
32	Correct	4 ms	2348 KB	Output is correct
33	Correct	4 ms	2348 KB	Output is correct
34	Correct	3 ms	2348 KB	Output is correct
35	Correct	4 ms	2348 KB	Output is correct
36	Correct	4 ms	2356 KB	Output is correct
37	Correct	4 ms	2360 KB	Output is correct
38	Correct	7 ms	2620 KB	Output is correct
39	Correct	6 ms	2620 KB	Output is correct
40	Correct	6 ms	2636 KB	Output is correct
41	Correct	6 ms	2692 KB	Output is correct
42	Correct	6 ms	2732 KB	Output is correct
43	Correct	4 ms	2772 KB	Output is correct
44	Correct	6 ms	2952 KB	Output is correct
45	Correct	6 ms	2952 KB	Output is correct
46	Correct	4 ms	3076 KB	Output is correct
47	Correct	5 ms	3076 KB	Output is correct
48	Correct	5 ms	3076 KB	Output is correct
49	Correct	4 ms	3208 KB	Output is correct
50	Correct	6 ms	3208 KB	Output is correct
51	Correct	5 ms	3316 KB	Output is correct

Subtask #4
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1912 KB	Output is correct
2	Correct	3 ms	1912 KB	Output is correct
3	Correct	3 ms	1952 KB	Output is correct
4	Correct	3 ms	2008 KB	Output is correct
5	Correct	3 ms	2012 KB	Output is correct
6	Correct	3 ms	2020 KB	Output is correct
7	Correct	3 ms	2072 KB	Output is correct
8	Correct	3 ms	2112 KB	Output is correct
9	Correct	3 ms	2132 KB	Output is correct
10	Correct	3 ms	2136 KB	Output is correct
11	Correct	3 ms	2196 KB	Output is correct
12	Correct	3 ms	2196 KB	Output is correct
13	Correct	3 ms	2196 KB	Output is correct
14	Correct	3 ms	2340 KB	Output is correct
15	Correct	3 ms	2340 KB	Output is correct
16	Correct	4 ms	2340 KB	Output is correct
17	Correct	4 ms	2340 KB	Output is correct
18	Correct	4 ms	2340 KB	Output is correct
19	Correct	3 ms	2340 KB	Output is correct
20	Correct	3 ms	2348 KB	Output is correct
21	Correct	3 ms	2348 KB	Output is correct
22	Correct	3 ms	2348 KB	Output is correct
23	Correct	3 ms	2348 KB	Output is correct
24	Correct	3 ms	2348 KB	Output is correct
25	Correct	3 ms	2348 KB	Output is correct
26	Correct	3 ms	2348 KB	Output is correct
27	Correct	3 ms	2348 KB	Output is correct
28	Correct	3 ms	2348 KB	Output is correct
29	Correct	4 ms	2348 KB	Output is correct
30	Correct	3 ms	2348 KB	Output is correct
31	Correct	4 ms	2348 KB	Output is correct
32	Correct	4 ms	2348 KB	Output is correct
33	Correct	4 ms	2348 KB	Output is correct
34	Correct	3 ms	2348 KB	Output is correct
35	Correct	4 ms	2348 KB	Output is correct
36	Correct	4 ms	2356 KB	Output is correct
37	Correct	4 ms	2360 KB	Output is correct
38	Correct	7 ms	2620 KB	Output is correct
39	Correct	6 ms	2620 KB	Output is correct
40	Correct	6 ms	2636 KB	Output is correct
41	Correct	6 ms	2692 KB	Output is correct
42	Correct	6 ms	2732 KB	Output is correct
43	Correct	4 ms	2772 KB	Output is correct
44	Correct	6 ms	2952 KB	Output is correct
45	Correct	6 ms	2952 KB	Output is correct
46	Correct	4 ms	3076 KB	Output is correct
47	Correct	5 ms	3076 KB	Output is correct
48	Correct	5 ms	3076 KB	Output is correct
49	Correct	4 ms	3208 KB	Output is correct
50	Correct	6 ms	3208 KB	Output is correct
51	Correct	5 ms	3316 KB	Output is correct
52	Correct	258 ms	20688 KB	Output is correct
53	Correct	245 ms	26344 KB	Output is correct
54	Correct	190 ms	31228 KB	Output is correct
55	Correct	183 ms	36320 KB	Output is correct
56	Correct	196 ms	41708 KB	Output is correct
57	Correct	175 ms	46856 KB	Output is correct
58	Correct	175 ms	52540 KB	Output is correct
59	Correct	218 ms	57740 KB	Output is correct
60	Correct	167 ms	62652 KB	Output is correct
61	Correct	185 ms	67680 KB	Output is correct
62	Correct	199 ms	72720 KB	Output is correct
63	Correct	147 ms	80060 KB	Output is correct
64	Correct	154 ms	81956 KB	Output is correct
65	Correct	217 ms	88320 KB	Output is correct
66	Correct	199 ms	94076 KB	Output is correct
67	Correct	212 ms	99972 KB	Output is correct
68	Correct	223 ms	105732 KB	Output is correct
69	Correct	231 ms	111260 KB	Output is correct
70	Correct	212 ms	116752 KB	Output is correct
71	Correct	225 ms	122220 KB	Output is correct
72	Correct	227 ms	127600 KB	Output is correct
73	Correct	237 ms	133232 KB	Output is correct
74	Correct	225 ms	138860 KB	Output is correct
75	Correct	218 ms	144404 KB	Output is correct
76	Correct	247 ms	150140 KB	Output is correct
77	Correct	177 ms	155644 KB	Output is correct
78	Correct	185 ms	161240 KB	Output is correct
79	Correct	224 ms	166360 KB	Output is correct
80	Correct	217 ms	171392 KB	Output is correct

답안 #44787

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 30.0 / 30.0

Subtask #3 25.0 / 25.0

Subtask #4 29.0 / 29.0

Subtask #1
16.0 / 16.0

Subtask #2
30.0 / 30.0

Subtask #3
25.0 / 25.0

Subtask #4
29.0 / 29.0