Submission #431875

#	Time	Username	Problem	Language	Result	Execution time	Memory
431875		lyc	Long Distance Coach (JOI17_coach)	C++14	71 / 100	2089 ms	33748 KiB

coach

#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];

ll cnt[2005][2005], pref[2005];

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);
    
    FOR(j,0,N+1){
        FOR(i,1,M){
            auto [D,C] = cus[i];
            cnt[j][i] = (S[j]-D)/T + cnt[j][i-1];
        }
    }
    FOR(i,1,M){
        pref[i] = cus[i].second + pref[i-1];
    }

    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;
            //}
            cost += pref[lst[j]]-pref[i-1];
            cost -= (cnt[N+1][lst[j]]-cnt[N+1][i-1] 
                    - (cnt[j+1][lst[j]]-cnt[j+1][i-1])
                    + lst[j]-i+1) * W;
            //TRACE(i _ j _ cost);
            dp[i] = min(dp[i],dp[lst[j]+1]+cost);
        }
    }

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

Compilation message (stderr)

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

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