#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 2e18;
const int MAXN = 2e5 + 5;
template<typename A, typename B>
void chmin(A &a, const B &b) { a = min(a, b); }
template<typename A, typename B>
void chmax(A &a, const B &b) { a = max(a, b); }
struct Line {
lint a, b;
Line() : a(0), b(INF) {}
Line(lint a, lint b) : a(a), b(b) {}
lint get(lint x) {
return a * x + b;
}
};
class LiChao {
private:
struct Node {
Line line = Line();
Node *lc = nullptr;
Node *rc = nullptr;
};
lint sz;
Node *root = nullptr;
void InsertLineKnowingly(Node* &n, lint tl, lint tr, Line x) {
if (n == nullptr) n = new Node();
if (n->line.get(tl) > x.get(tl)) swap(n->line, x);
if (n->line.get(tr) <= x.get(tr)) return;
if (tl == tr) return;
lint mid = (tl + tr) / 2;
if (n->line.get(mid) < x.get(mid)) {
InsertLineKnowingly(n->rc, mid + 1, tr, x);
} else {
swap(n->line, x);
InsertLineKnowingly(n->lc, tl, mid, x);
}
}
void InsertLine(Node* &n, lint tl, lint tr, lint l, lint r, Line x) {
if (tr < l || r < tl || tl > tr || l > r) return;
if (n == nullptr) n = new Node();
if (l <= tl && tr <= r) return InsertLineKnowingly(n, tl, tr, x);
lint mid = (tl + tr) / 2;
InsertLine(n->lc, tl, mid, l, r, x);
InsertLine(n->rc, mid + 1, tr, l, r, x);
}
lint Query(Node* &n, lint tl, lint tr, lint x) {
if (n == nullptr) return INF;
if (tl == tr) return n->line.get(x);
lint res = n->line.get(x);
lint mid = (tl + tr) / 2;
if (x <= mid) {
res = min(res, Query(n->lc, tl, mid, x));
} else {
res = min(res, Query(n->rc, mid + 1, tr, x));
}
return res;
}
public:
LiChao() {}
LiChao(lint sz) : sz(sz) {}
vector<Line> all;
void InsertLine(lint l, lint r, Line x) {
return InsertLine(root, 0, sz - 1, l, r, x);
}
lint Query(lint x) {
return min(INF, Query(root, 0, sz - 1, x));
}
};
int N, M;
lint X, W, T;
LiChao li_chao(INF);
lint S[MAXN], P[MAXN];
pair<lint, lint> A[MAXN];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> X >> N >> M >> W >> T;
for (int i = 0; i < N; i++) {
cin >> S[i];
}
S[N] = X;
vector<int> order(N + 1);
iota(begin(order), end(order), 0);
sort(begin(order), end(order), [&](int i, int j) {
return (S[i] % T) < (S[j] % T);
});
for (int i = 0; i < M; i++) {
cin >> A[i].first >> A[i].second;
}
sort(A, A + M);
for (int i = 0; i < M; i++) {
P[i + 1] = P[i] + A[i].second;
}
// vector<vector<pair<int, lint>>> adj(M + 1);
// for (int i = 0; i <= N; i++) {
// int p = upper_bound(A, A + M, make_pair(S[i] % T, -1ll)) - A;
// lint total_weight = 0;
// for (int j = p - 1; j >= 0; j--) {
// lint weight = A[j].second + S[i] / T * W;
// total_weight += weight;
// adj[j].emplace_back(p, total_weight);
// }
// }
// At time t1 delete [a, b].
// At time t2 delete [c, d].
// Then [a, b] and [c, d] will never overlap in optimal answer.
// If they overlap, we can delete the overlapping region at min(t1, t2) to get more benefit.
// This is possible since we can keep extending both a and b to the left until 0.
vector<lint> dp(M + 1, INF);
dp[0] = (X + T - 1) / T * W;
for (int i = 0, ptr = 0; i < M; i++) {
chmin(dp[i + 1], dp[i] + (X + T - 1 - A[i].first) / T * W);
// li_chao.InsertLine(0, INF - 1, Line(-i, dp[i] - P[i]));
for (int ptr = 0; ptr <= N; ptr++) {
int p = upper_bound(A, A + M, make_pair(S[ptr] % T, -1ll)) - A;
if (p < i + 1) {
ptr += 1;
continue;
}
if (p == i + 1) {
// lint x = S[ptr] / T * W;
// chmin(dp[i + 1], (i + 1) * x + P[i + 1] + li_chao.Query(x));
lint total_weight = 0;
for (int j = i; j >= 0; j--) {
lint weight = A[j].second + S[ptr] / T * W;
total_weight += weight;
chmin(dp[i + 1], dp[j] + total_weight);
}
ptr += 1;
} else {
break;
}
}
}
cout << dp[M] << "\n";
return 0;
}
Compilation message
coach.cpp: In function 'int main()':
coach.cpp:130:19: warning: unused variable 'ptr' [-Wunused-variable]
130 | for (int i = 0, ptr = 0; i < M; i++) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
