#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll
using namespace std;
typedef long long ll;
typedef long double ld;
int inf = (1LL << 62);
const int N = (1 << 18);
struct line {
int k, b;
int get(int x) {
return k * x + b;
}
bool operator < (const line& x) const {
return k < x.k;
}
};
struct node {
node* l;
node* r;
line now;
node(node* _l, node* _r, line _now) : l(_l), r(_r), now(_now) {}
};
struct lichao {
node* v;
lichao() {
v = new node(NULL, NULL, {0, inf});
}
int get(node* v, int l, int r, int x) {
int ans = v->now.get(x);
int m = (l + r) / 2;
if(m <= x) {
if(v->r == NULL)
return ans;
else
return min(ans, get(v->r, m, r, x));
}
else {
if(v->l == NULL)
return ans;
else
return min(ans, get(v->l, l, m, x));
}
}
void upd(node* v, int l, int r, line val) {
int m = (l + r) / 2;
bool lft = val.get(l) < v->now.get(l);
bool mid = val.get(m) < v->now.get(m);
if(mid)
swap(v->now, val);
if(r - l == 1)
return;
if(lft == mid) {
if(v->r == NULL) {
auto neww = new node(NULL, NULL, {0, inf});
v->r = neww;
}
upd(v->r, m, r, val);
return;
}
else {
if(v->l == NULL) {
auto neww = new node(NULL, NULL, {0, inf});
v->l = neww;
}
upd(v->l, l, m, val);
return;
}
}
int get(int x) {
return get(v, 0, inf, x);
}
void upd(line val) {
upd(v, 0, inf, val);
}
};
lichao tree[2 * N];
int get(int v, int l, int r, int vl, int vr, int X) {
if(r <= vl || vr <= l)
return inf;
if(vl <= l && r <= vr) {
return tree[v].get(X);
}
int m = (l + r) / 2;
return min(get(v * 2, l, m, vl, vr, X), get(v * 2, m, r, vl, vr, X));
}
void upd(int v, line val) {
if(v == 0)
return;
tree[v].upd(val);
upd(v / 2, val);
return;
}
signed main() {
#ifdef PC
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int x, n, m, w, T;
cin >> x >> n >> m >> w >> T;
vector<int> s(n + 1);
vector<pair<int, int>> p(m);
vector<int> pref(m + 1, 0);
vector<int> cnt(m + 1, 0);
vector<int> d(m + 1, 0);
s[0] = 0;
for (int i = 1; i <= n; i++)
cin >> s[i];
s.pb(x);
n += 2;
sort(s.begin(), s.end());
for (int i = 0; i < m; i++) {
cin >> p[i].ft >> p[i].sc;
}
sort(p.begin(), p.end());
for (int i = 0; i < m; i++) {
pref[i + 1] = pref[i] + p[i].sc;
cnt[i] = (x - p[i].ft) / T + 1;
d[i] = p[i].ft;
}
vector<vector<pair<int, int>>> can(m + 1);
for (int i = 1; i < n; i++) {
int driver = s[i] / T * T;
int lstt = -1, lst = -1;
for (int j = 0; j < m; j++) {
int time = s[i] / T * T + d[j];
if(time > s[i])
time -= T;
if(time < s[i - 1])
continue;
if(time < driver)
continue;
if(time > lstt) {
lstt = time;
lst = j;
}
}
if(lstt == -1)
continue;
int minn = lst;
for (int j = m - 1; j >= 0; j--) {
int time = s[i] / T * T + d[j];
if(time > s[i])
time -= T;
if(time < s[i - 1])
continue;
if(time < driver)
continue;
minn = min(j, minn);
// can[lst].pb({s[i], j});
}
can[lst].pb({s[i], minn});
}
vector<int> dp(m + 1, 0);
for (int i = 0; i < m; i++) {
dp[i + 1] = dp[i] + cnt[i] * w;
int add = 0;
upd(N + i, {-i, -pref[i] + dp[i]});
for (auto x : can[i]) {
int time = x.ft / T * T + d[i];
if(time > x.ft)
time -= T;
int X = time / T * w;
dp[i + 1] = min(dp[i + 1], pref[i + 1] + (i + 1) * X + get(1, 0, N, x.sc, i + 1, X));
}
// cout << i << " " << dp[i + 1] << endl;
}
cout << dp[m] + ((x / T + 1) * w) << endl;
return 0;
}
Compilation message
coach.cpp: In function 'int main()':
coach.cpp:190:7: warning: unused variable 'add' [-Wunused-variable]
int add = 0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
29048 KB |
Output is correct |
| 2 |
Correct |
33 ms |
29048 KB |
Output is correct |
| 3 |
Correct |
30 ms |
29048 KB |
Output is correct |
| 4 |
Correct |
29 ms |
29048 KB |
Output is correct |
| 5 |
Incorrect |
29 ms |
29304 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
29048 KB |
Output is correct |
| 2 |
Correct |
33 ms |
29048 KB |
Output is correct |
| 3 |
Correct |
30 ms |
29048 KB |
Output is correct |
| 4 |
Correct |
29 ms |
29048 KB |
Output is correct |
| 5 |
Incorrect |
29 ms |
29304 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
29048 KB |
Output is correct |
| 2 |
Correct |
33 ms |
29048 KB |
Output is correct |
| 3 |
Correct |
30 ms |
29048 KB |
Output is correct |
| 4 |
Correct |
29 ms |
29048 KB |
Output is correct |
| 5 |
Incorrect |
29 ms |
29304 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
29048 KB |
Output is correct |
| 2 |
Correct |
33 ms |
29048 KB |
Output is correct |
| 3 |
Correct |
30 ms |
29048 KB |
Output is correct |
| 4 |
Correct |
29 ms |
29048 KB |
Output is correct |
| 5 |
Incorrect |
29 ms |
29304 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
