답안 #600639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600639	2022-07-21T06:36:39 Z	이동현(#8470)	Long Distance Coach (JOI17_coach)	C++17	46 / 100	2000 ms	5188 KB

coach

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

const int NS = (int)2e5 + 4;
int x, n, m, w, t;
int r[NS];
int s[NS];
vector<int> peo[NS];
int dp[NS], vala[NS], valb[NS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> x >> n >> m >> w >> t;
    for(int i = 1; i <= n; ++i){
        cin >> s[i];
    }
    ++n; s[n] = x;
    for(int i = 1; i <= m; ++i){
        peo[i].resize(2);
        cin >> peo[i][0] >> peo[i][1];
    }
    sort(s + 1, s + n + 1, [&](int&x, int&y){return x % t < y % t;});
    sort(peo + 1, peo + m + 1);
    int pp = 0;
    for(int i = 1; i <= n; ++i){
        while(pp + 1 <= m && peo[pp + 1][0] < s[i] % t){
            ++pp;
        }
        r[i] = pp;
    }
    auto eat = [&](int all, int me)->int{
        if(all >= me) return (all - me) / t + 1;
        return 0;
    };
    int nodie = 0;
    for(int j = 1; j <= m; ++j){
        nodie += w * eat(x, peo[j][0]);
    }
    int ans = nodie;
    for(int i = 1; i <= n; ++i){
        dp[i] = (int)1e18;
        for(int j = 0; j < i; ++j){
            int sum = 0;
            for(int k = r[j] + 1; k <= r[i]; ++k){
                vala[k] = w * eat(x, peo[k][0]);
                valb[k] = peo[k][1] + w * eat(s[i] / t * t, peo[k][0]);
                sum += vala[k];
            }
            for(int k = r[i]; k > r[j]; --k){
                sum += valb[k] - vala[k];
                dp[i] = min(dp[i], dp[j] + sum);
            }
        }
        int nval = dp[i];
        for(int j = r[i] + 1; j <= m; ++j){
            nval += w * eat(x, peo[j][0]);
        }
        ans = min(ans, nval);
    }
    ans += w * eat(x, 0);
    cout << ans << '\n';
    return 0;
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4948 KB	Output is correct
2	Correct	4 ms	4948 KB	Output is correct
3	Correct	4 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	4 ms	4948 KB	Output is correct
7	Correct	3 ms	4952 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	5016 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4948 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	3 ms	5032 KB	Output is correct
15	Correct	4 ms	4948 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	4 ms	4948 KB	Output is correct
18	Correct	4 ms	4948 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	3 ms	4948 KB	Output is correct
21	Correct	3 ms	4948 KB	Output is correct
22	Correct	3 ms	4948 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4948 KB	Output is correct
2	Correct	4 ms	4948 KB	Output is correct
3	Correct	4 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	4 ms	4948 KB	Output is correct
7	Correct	3 ms	4952 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	5016 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4948 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	3 ms	5032 KB	Output is correct
15	Correct	4 ms	4948 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	4 ms	4948 KB	Output is correct
18	Correct	4 ms	4948 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	3 ms	4948 KB	Output is correct
21	Correct	3 ms	4948 KB	Output is correct
22	Correct	3 ms	4948 KB	Output is correct
23	Correct	5 ms	4948 KB	Output is correct
24	Correct	6 ms	5028 KB	Output is correct
25	Correct	5 ms	5032 KB	Output is correct
26	Correct	5 ms	4948 KB	Output is correct
27	Correct	5 ms	5036 KB	Output is correct
28	Correct	5 ms	4948 KB	Output is correct
29	Correct	7 ms	4948 KB	Output is correct
30	Correct	6 ms	5028 KB	Output is correct
31	Correct	5 ms	4948 KB	Output is correct
32	Correct	6 ms	5076 KB	Output is correct
33	Correct	7 ms	5076 KB	Output is correct
34	Correct	5 ms	5040 KB	Output is correct
35	Correct	6 ms	5036 KB	Output is correct
36	Correct	5 ms	4948 KB	Output is correct
37	Correct	6 ms	4948 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4948 KB	Output is correct
2	Correct	4 ms	4948 KB	Output is correct
3	Correct	4 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	4 ms	4948 KB	Output is correct
7	Correct	3 ms	4952 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	5016 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4948 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	3 ms	5032 KB	Output is correct
15	Correct	4 ms	4948 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	4 ms	4948 KB	Output is correct
18	Correct	4 ms	4948 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	3 ms	4948 KB	Output is correct
21	Correct	3 ms	4948 KB	Output is correct
22	Correct	3 ms	4948 KB	Output is correct
23	Correct	5 ms	4948 KB	Output is correct
24	Correct	6 ms	5028 KB	Output is correct
25	Correct	5 ms	5032 KB	Output is correct
26	Correct	5 ms	4948 KB	Output is correct
27	Correct	5 ms	5036 KB	Output is correct
28	Correct	5 ms	4948 KB	Output is correct
29	Correct	7 ms	4948 KB	Output is correct
30	Correct	6 ms	5028 KB	Output is correct
31	Correct	5 ms	4948 KB	Output is correct
32	Correct	6 ms	5076 KB	Output is correct
33	Correct	7 ms	5076 KB	Output is correct
34	Correct	5 ms	5040 KB	Output is correct
35	Correct	6 ms	5036 KB	Output is correct
36	Correct	5 ms	4948 KB	Output is correct
37	Correct	6 ms	4948 KB	Output is correct
38	Execution timed out	2074 ms	5188 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

Subtask #4
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4948 KB	Output is correct
2	Correct	4 ms	4948 KB	Output is correct
3	Correct	4 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	4 ms	4948 KB	Output is correct
7	Correct	3 ms	4952 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	5016 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4948 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	3 ms	5032 KB	Output is correct
15	Correct	4 ms	4948 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	4 ms	4948 KB	Output is correct
18	Correct	4 ms	4948 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	3 ms	4948 KB	Output is correct
21	Correct	3 ms	4948 KB	Output is correct
22	Correct	3 ms	4948 KB	Output is correct
23	Correct	5 ms	4948 KB	Output is correct
24	Correct	6 ms	5028 KB	Output is correct
25	Correct	5 ms	5032 KB	Output is correct
26	Correct	5 ms	4948 KB	Output is correct
27	Correct	5 ms	5036 KB	Output is correct
28	Correct	5 ms	4948 KB	Output is correct
29	Correct	7 ms	4948 KB	Output is correct
30	Correct	6 ms	5028 KB	Output is correct
31	Correct	5 ms	4948 KB	Output is correct
32	Correct	6 ms	5076 KB	Output is correct
33	Correct	7 ms	5076 KB	Output is correct
34	Correct	5 ms	5040 KB	Output is correct
35	Correct	6 ms	5036 KB	Output is correct
36	Correct	5 ms	4948 KB	Output is correct
37	Correct	6 ms	4948 KB	Output is correct
38	Execution timed out	2074 ms	5188 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

답안 #600639

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 30.0 / 30.0

Subtask #3 0 / 25.0

Subtask #4 0 / 29.0

Subtask #1
16.0 / 16.0

Subtask #2
30.0 / 30.0

Subtask #3
0 / 25.0

Subtask #4
0 / 29.0