Submission #69460

#	Time	Username	Problem	Language	Result	Execution time	Memory
69460		Benq	Long Distance Coach (JOI17_coach)	C++14	71 / 100	2054 ms	15112 KiB

coach

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 4e18;
const int MX = 200001;

ll X,N,M,W,T,dp[MX];
vl S;
vpl D;

void mn(ll& a, ll b) { a = min(a,b); }

int getLst(ll x) {
    return lb(all(D),mp(x%T,0LL))-D.begin()-1;
}

ll cost[MX];

void genCost (int a) {
    F0Rd(i,sz(S)) if (getLst(S[i]) == a) 
        FOR(j,getLst(S[i])+1,M+1) mn(cost[j],S[i]/T*W);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> X >> N >> M >> W >> T; 
    S.resize(N+1); F0R(i,N) cin >> S[i];
    S[N] = X;
    D.resize(M+1); F0R(i,M) cin >> D[i].f >> D[i].s;
    D[M] = {T,0};
    
    sort(all(D));
    
    F0R(i,M+1) dp[i] = cost[i] = INF;
    dp[M] = (X/T+1)*W;
    F0Rd(i,M) {
        genCost(i);
        FOR(j,i+1,M+1) {
            mn(dp[i],dp[j]); 
            dp[j] += D[i].s+cost[j]; mn(dp[j],INF);
        }
        dp[i] += ((X-D[i].f)/T+1)*W;
        /*F0R(j,M+1) cout << cost[j] << " ";
        cout << "\n";
        F0R(j,M+1) cout << dp[j] << " ";
        cout << "\n\n";*/
    }
    ll ans = INF; F0R(i,M+1) mn(ans,dp[i]);
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

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