#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
#define endl '\n'
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
int x, n, m, w, t;
cin >> x >> n >> m >> w >> t;
//first - d, second - c
vector <int> s(n);
for (int i = 0; i < n; ++i)
cin >> s[i];
sort(all(s));
s.app(x);
vector <ii> a(m);
for (int i = 0; i < m; ++i)
cin >> a[i].f >> a[i].s;
sort(all(a));
reverse(all(a));
a.insert(a.begin(), mp(0, 0));
map <int, int> pos;
for (int i = 0; i < a.size(); ++i)
pos[a[i].f] = i;
vector <int> c;
for (auto e : a)
c.app(e.f);
sort(all(c));
vector <int> last(s.size()), mem(a.size(), s.size());
for (int i = 0; i < s.size(); ++i) {
int p = lower_bound(all(c), s[i]%t) - c.begin();
p = (p - 1 + c.size()) % c.size();
last[i] = pos[c[p]];
mem[last[i]] = min(mem[last[i]], i);
}
vector <int> dp(a.size()+1);
vector <int> rel(a.size()+1);
rel[0] = dp[0] = (x/t+1)*w;
const int INF = 1e9;
vector <ii> lf;
for (int j = 1; j <= a.size(); ++j) {
if (mem[j-1] != s.size()) {
auto add = mp(mem[j-1], j-1);
while (lf.size() && add < lf.back()) {
lf.pop_back();
}
lf.app(add);
}
if (lf.empty()) {
for (int i = 0; i < j - 1; ++i)
rel[i] = -1;
}
else {
lf.back().s = j-1;
}
int l = 0;
for (auto e : lf) {
int lf = e.f;
for (int i = l; i < e.s; ++i) {
if (rel[i] != -1) {
rel[i] += a[j-1].s;
if (s[lf] > a[j-1].f)
rel[i] += (s[lf]/t+a[j-1].f/t+(s[lf]<a[j-1].f))*w;
}
}
l = e.s;
}
int save = 0;
if (j < a.size())
save = (x/t+(a[j].f<=(x%t)))*w;
int mn = -1;
for (int i = 0; i < j; ++i) {
if (rel[i] != -1) {
if (mn == -1 || rel[i] + save < mn) {
mn = rel[i] + save;
}
}
}
dp[j] = rel[j] = mn;
//cout << j << " : " << dp[j] << endl;
}
cout << (int)dp[a.size()] << endl;
}
Compilation message
coach.cpp: In function 'int main()':
coach.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); ++i)
~~^~~~~~~~~~
coach.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); ++i) {
~~^~~~~~~~~~
coach.cpp:61:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j <= a.size(); ++j) {
~~^~~~~~~~~~~
coach.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (mem[j-1] != s.size()) {
coach.cpp:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (j < a.size())
~~^~~~~~~~~~
coach.cpp:59:15: warning: unused variable 'INF' [-Wunused-variable]
const int INF = 1e9;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
