제출 #431688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431688		lyc	Long Distance Coach (JOI17_coach)	C++14	0 / 100	1 ms	332 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];

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';
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 29