/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2005, M = 1e5+10, K = 52, MX = 30;
const ll INF = 1e18;
ll X, n, m, W, T, ans, pref[N];
ll s[N], DP[N], cost[N][N];
array<ll, 2> a[N];
void solve(){
cin >> X >> n >> m >> W >> T;
for(int i = 1; i <= n; ++i){
cin >> s[i];
}
ans = X / T + 1;
for(int i = 1; i <= m; ++i){
cin >> a[i][0] >> a[i][1];
ans += (X - a[i][0] + T - 1) / T;
}
ans *= W;
sort(a+1, a+1+m);
pref[0] = 0;
for(int i = 1; i <= m; ++i){
pref[i] = pref[i - 1] + a[i][1];
}
for(int i = 0; i <= m; ++i){
for(int j = 0; j <= m; ++j){
cost[i][j] = INF;
}
DP[i] = 0;
}
int L = lower_bound(a+1, a+1+m, array<ll, 2>{X%T, -1}) - a; --L;
vector<ll> A(m + 1, -37);
s[n + 1] = X;
for(int i = 1; i <= n + 1; ++i){
int pos = lower_bound(a+1, a+1+m, array<ll, 2>{s[i] % T, -1}) - a;
--pos;
int r = pos;
if(A[r] == -37)
A[r] = ((X - ((s[i] / T) * T + a[r][0]) + T - 1) / T);
// ll cur_sum = 0;
// for(int l = r; l >= 1; --l){
// cur_sum += (X - ((s[i] / T) * T + a[l][0]) + T - 1) / T;
// cost[l][r] = min(cost[l][r], - W * cur_sum);
// // cerr << i << ' ' << l << ' ' << r << ' ' << -W * cur_sum << ' ' << -W*cur_sum + pref[r]-pref[l-1] << '\n';
// }
}
// for(int i = 1; i <= m; ++i){
// for(int j = 1; j <= i; ++j){
// cerr << i << ' ' << j << ' ' << cost[j][i] << ' ' << cost[j][i] + pref[i] - pref[j - 1] << '\n';
// }
// cerr << '\n';
// }
for(int i = 1; i <= m; ++i){
DP[i] = DP[i - 1] + pref[i - 1];
if(A[i] == -37){
// cerr << DP[i] << ' ';
DP[i] -= pref[i];
continue;
}
for(int j = 0; j < i; ++j){
if(i > L)
DP[i] = min(DP[i], DP[j] + -(j >= L ? (i - j) * A[i] : (i - L) * A[i] + (A[i] + 1) * (L-j)) * W + pref[i]);
else
DP[i] = min(DP[i], DP[j] + pref[i] - W * (i - j) * A[i]);
}
// cerr << DP[i] << ' ';
DP[i] -= pref[i];
}
cout << ans + DP[m] + pref[m];
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |