oj.uz

Submission #431688

# Submission time Handle Problem Language Result Execution time Memory
431688 2021-06-17T14:30:09 Z lyc Long Distance Coach (JOI17_coach) C++14
0 / 100
 1 ms 332 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];
    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/W);
    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:59:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |                 auto [D,C] = cus[k];
      |                      ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -