oj.uz

Submission #431858

# Submission time Handle Problem Language Result Execution time Memory
431858 2021-06-17T16:15:51 Z lyc Long Distance Coach (JOI17_coach) C++14
46 / 100
 2000 ms 420 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<ll,ll> pll;

const int mxN = 2e5+5;
const int mxM = 2e5+5;

ll X, T, S[mxN];
int N, M, W;
pll cus[mxM];

int fst[mxN], lst[mxN];
ll base, dp[mxM];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> X >> N >> M >> W >> T;
    FOR(i,1,N) cin >> S[i];
    sort(S+1,S+1+N);
    S[0] = 1; S[N+1] = X;
    FOR(i,1,M){
        ll D, C; cin >> D >> C;
        cus[i] = pll(D,C);
    }
    sort(cus+1,cus+1+M);

    base = W;
    FOR(i,0,N){
        ll a = (S[i]+T-1)/T, b = S[i+1]/T, cur = 0;
        if (a > b) {
            fst[i] = lower_bound(cus+1,cus+1+M,pll(S[i]%T,0)) - cus;
            lst[i] = lower_bound(cus+1,cus+1+M,pll(S[i+1]%T,0)) - cus - 1;
        } else {
            cur += (b-a) * (M+1) + 1;
            cur += (cus+1+M) - lower_bound(cus+1,cus+1+M,pll(S[i]%T,0));
            fst[i] = 1;
            lst[i] = lower_bound(cus+1,cus+1+M,pll(S[i+1]%T,0)) - cus - 1;
        }
        cur += lst[i]-fst[i]+1;
        base += cur * W;
        //TRACE(i _ a _ b _ cur _ fst[i] _ lst[i] _ lst[i]-fst[i]+1);
    }

    //TRACE(base);
    dp[M+1] = base;
    RFOR(i,M,1){
        dp[i] = dp[i+1];
        FOR(j,0,N) if (fst[j] <= i && i <= lst[j]) {
            ll cost = 0;
            FOR(k,i,lst[j]){
                auto [D,C] = cus[k];
                cost += C;
                cost -= ((X-D)/T - (S[j+1]-D)/T + 1) * W;
            }
            //TRACE(i _ j _ cost);
            dp[i] = min(dp[i],dp[lst[j]+1]+cost);
        }
    }

    cout << dp[1] << '\n';
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:60:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |                 auto [D,C] = cus[k];
      |                      ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 3 ms 324 KB Output is correct
27 Correct 3 ms 332 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 5 ms 332 KB Output is correct
30 Correct 5 ms 332 KB Output is correct
31 Correct 4 ms 332 KB Output is correct
32 Correct 4 ms 332 KB Output is correct
33 Correct 4 ms 332 KB Output is correct
34 Correct 2 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 3 ms 332 KB Output is correct
37 Correct 4 ms 332 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 3 ms 324 KB Output is correct
27 Correct 3 ms 332 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 5 ms 332 KB Output is correct
30 Correct 5 ms 332 KB Output is correct
31 Correct 4 ms 332 KB Output is correct
32 Correct 4 ms 332 KB Output is correct
33 Correct 4 ms 332 KB Output is correct
34 Correct 2 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 3 ms 332 KB Output is correct
37 Correct 4 ms 332 KB Output is correct
38 Execution timed out 2076 ms 420 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 3 ms 324 KB Output is correct
27 Correct 3 ms 332 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 5 ms 332 KB Output is correct
30 Correct 5 ms 332 KB Output is correct
31 Correct 4 ms 332 KB Output is correct
32 Correct 4 ms 332 KB Output is correct
33 Correct 4 ms 332 KB Output is correct
34 Correct 2 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 3 ms 332 KB Output is correct
37 Correct 4 ms 332 KB Output is correct
38 Execution timed out 2076 ms 420 KB Time limit exceeded
39 Halted 0 ms 0 KB -