| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1234833 | PenguinsAreCute | Long Distance Coach (JOI17_coach) | C++17 | 0 ms | 0 KiB |
struct seg {
int n;
vector<long long> val;
seg(int _n): n(_n), val(2*_n,1e18) {}
void up(int x, long long u) {
for(x+=n;x;x>>=1)
val[x] = min(val[x], u);
}
long long qry(int l, int r) {
long long ans = 1e18;
for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
if(l&1)
ans=min(ans,val[l++]);
if(r&1)
ans=min(ans,val[--r]);
}
return ans;
}
};
int main() {
long long x, t, w;
int n, m;
cin >> x >> n >> m >> w >> t;
seg tree(n+1);
long long s[n+1];
for(int i=0;i<n;i++)
cin >> s[i];
s[n++] = x;
long long u[n];
memcpy(u,s,sizeof(u));
for(int i=0;i<n;i++)
u[i] %= t;
sort(u,u+n);
for(int i=0;i<n;i++) {
int id = lower_bound(u,u+n+1,s[i]%t)-u;
tree.up(id,s[i]);
}
pair<long long, long long> ppl[m+1];
for(int i=0;i<m;i++)
cin >> ppl[i].first >> ppl[i].second;
ppl[m++] = {0, 1e18};
long long d[m], c[m];
sort(s,s+n);
sort(ppl,ppl+m);
for(int i=0;i<m;i++)
d[i] = ppl[i].first, c[i] = ppl[i].second;
pair<long long,int> dp[m+1];
fill(dp,dp+m+1,make_pair((long long)1e18,0));
dp[m] = {0,m};
for(int i=m;i;i--) {
long long cur = 0;
for(int j=i;j--;) {
dp[j] = min(dp[j], {dp[i].first + cur, i});
long long minT = tree.qry(lower_bound(u,u+n,d[j])-u,i==m?n:lower_bound(u,u+n,d[i])-u);
minT -= (minT % t);
minT += d[j];
if(minT < 1e17)
cur += c[j] - (x - minT) / t * w - w;
else
cur = 1e18;
}
}
for(int i=0;i<m;i++)
assert(dp[i].second == i+1 || dp[i].second >= dp[i+1].second);
long long ans = dp[0].first;
for(int i=0;i<m;i++)
ans += w * ((x - d[i]) / t + 1);
cout << ans;
}