Submission #826395

#TimeUsernameProblemLanguageResultExecution timeMemory
826395MohamedAhmed04Long Distance Coach (JOI17_coach)C++14
71 / 100
2059 ms14704 KiB
#include <bits/stdc++.h> using namespace std ; const long long inf = 1e18 ; const int MAX = 2e5 + 10 ; long long arr[MAX] ; int n , m ; long long x , t , w ; vector< pair<long long , long long> >vp ; long long val[MAX] , pref[MAX] ; long long dp[MAX] ; int main() { ios_base::sync_with_stdio(0) ; cin.tie(0) ; cin>>x>>n>>m>>w>>t ; for(int i = 1 ; i <= n ; ++i) cin>>arr[i] ; for(int i = 1 ; i <= m ; ++i) { long long a , b ; cin>>a>>b ; vp.emplace_back(a , b) ; } vp.emplace_back(0 , 0) ; sort(arr+1 , arr+n+1) ; sort(vp.begin() , vp.end()) ; for(int i = 1 ; i <= m ; ++i) val[i] = inf , pref[i] = pref[i-1] + vp[i].second ; arr[n+1] = x ; for(int i = 1 ; i <= n+1 ; ++i) { int l = 1 , r = m ; int idx = -1 ; while(l <= r) { int mid = (l + r) >> 1 ; if(arr[i] % t >= vp[mid].first) idx = mid , l = mid+1 ; else r = mid-1 ; } if(idx != -1) val[idx] = min(val[idx] , arr[i] / t) ; } for(int i = 1 ; i <= m ; ++i) { dp[i] = dp[i-1] + x/t * w ; if(x%t > vp[i].first) dp[i] += w ; if(val[i] == inf) continue ; for(int j = i-1 ; j >= 0 ; --j) dp[i] = min(dp[i] , dp[j] + pref[i] - pref[j] + (i-j) * val[i] * w) ; } dp[m] += (x / t + 1) * w ; return cout<<dp[m]<<"\n" , 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...