#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct item * pitem;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
struct item {
pitem l=nullptr, r=nullptr;
ll a=0, b=INF;
};
ll T[LIM], dp[LIM], kiedy[LIM], pref[LIM], x, n, m, w, t, N=1;
pair<ll,ll>P[LIM];
ll ile(ll a, ll b, ll x) {
if(x==0 || a==0) return b;
if(a<0 && x<0) {
a*=-1; x*=-1;
}
if(a<0 || x<0) {
a=abs(a); x=abs(x);
if(INF/a<x) return -INF;
a*=-1;
} else {
if(INF/a<x) return INF;
}
a*=x; a+=b;
a=max(a, -INF);
a=min(a, INF);
return a;
}
void upd(pitem &v, ll l, ll r, ll a, ll b) {
if(l==r) {
if(ile(v->a, v->b, l)>ile(a, b, l)) {
v->a=a;
v->b=b;
return;
}
}
if(a==0 && b==INF) return;
ll mid=(l+r-1)/2;
if(ile(v->a, v->b, mid)>ile(a, b, mid)) {
swap(v->a, a);
swap(v->b, b);
}
if(a<v->a) {
if(!v->r) v->r=new item();
upd(v->r, mid+1, r, a, b);
} else {
if(!v->l) v->l=new item();
upd(v->l, l, mid, a, b);
}
}
ll cnt(pitem &v, ll l, ll r, ll x) {
if(!v) return INF;
ll ans=ile(v->a, v->b, x), mid=(l+r-1)/2;
if(l==r) return ans;
if(x<=mid) ans=min(ans, cnt(v->l, l, mid, x));
else ans=min(ans, cnt(v->r, mid+1, r, x));
return ans;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> x >> n >> m >> w >> t;
rep(i, 40) N*=2;
pitem root=new item();
rep(i, n) cin >> T[i];
T[n]=x; ++n;
rep(i, m) cin >> P[i].st >> P[i].nd;
sort(T, T+n);
sort(P, P+m);
rep(i, m) {
kiedy[i]=INF;
pref[i]=P[i].nd;
if(i) pref[i]+=pref[i-1];
}
rep(i, n) {
ll po=0, ko=m-1;
while(po<ko) {
ll sr=(po+ko+1)/2;
if(P[sr].st>T[i]%t) ko=sr-1; else po=sr;
}
if(P[po].st>T[i]%t) continue;
kiedy[po]=min(kiedy[po], T[i]/t);
}
rep(i, m) {
ll ile=w*(x/t);
if(x%t>P[i].st) ile+=w;
dp[i]=ile;
if(i) dp[i]+=dp[i-1];
if(kiedy[i]!=INF) {
dp[i]=min(dp[i], pref[i]+i*kiedy[i]*w+cnt(root, -N+1, 0, -kiedy[i]));
dp[i]=min(dp[i], pref[i]+(i+1)*kiedy[i]*w);
}
upd(root, -N+1, 0, i*w, dp[i]-pref[i]);
}
cout << dp[m-1]+w*(x/t+1) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
