제출 #1246607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246607		Zbyszek99	Long Distance Coach (JOI17_coach)	C++20	71 / 100	2096 ms	11652 KiB

coach

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

ll D[200002];
ll C[200002];
ll C_pref[200002];
int when_stop[200002];
ll dp[200002];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random();
    ll X,n,m,W,T;
    cin >> X >> n >> m >> W >> T;
    vl S(n);
    rep(i,n) cin >> S[i];
    rep(i,m) cin >> D[i] >> C[i];
    vector<pll> pas;
    rep(i,m) pas.pb({D[i],C[i]});
    pas.pb({0,(ll)1e18});
    sort(all(pas));
    S.pb(X);
    sort(all(S));
    m++;
    rep(i,m) 
    {
        D[i+1] = pas[i].ff;
        C[i+1] = pas[i].ss;
    }
    ll drinks = (X-D[m-1]+T-1)/T;
    ll ans = 0;
    rep2(i,1,m)
    {
        ll my_drinks = (X-D[i]+T-1)/T;
        ans += my_drinks*W;
        if(my_drinks != drinks)
        {
            C[i] -= W;
        }
    }
    int cur = 0;
    rep2(i,1,m) when_stop[i] = 1e9;
    forall(it,S)
    {
        int mod = it%T;
        int l = 1;
        int r = m;
        int ans = 1;
        while(l <= r)
        {
            int mid = (l+r)/2;
            if(D[mid] <= mod)
            {
                ans = mid;
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        when_stop[ans] = min(when_stop[ans],cur);
        cur++;
    }
    rep2(i,1,m) C_pref[i] = C_pref[i-1] + C[i]; 
    rep2(i,1,m)
    {
        dp[i] = dp[i-1];
        if(when_stop[i] == 1e9) continue;
        ll my_poz = S[when_stop[i]] - (S[when_stop[i]]-D[i]+T)%T;
        ll rest = (X-my_poz+T-1)/T;
        if((X-D[i]+T-1)/T != drinks) rest--;
        rep2(j,0,i-1)
        {
            dp[i] = min(dp[i],(dp[j]-C_pref[j])+(-W*i*rest+C_pref[i]) + W*j*rest);
        }
    }
    cout << ans+dp[m];
}

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