#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));
auto getcnt = [&](int x, int d) {
if (x < d)
return 0ll;
int k = (x-d)/t;
return k + 1;
};
auto get = [&](int i, int j, int p) {
int di = a[i].f;
int dj = a[j%a.size()].f;
return a[j].s + (getcnt(s[p], dj)-1)*w;
};
auto save = [&](int i) {
if (i == a.size())
return 0ll;
int cnt = x/t+(a[i].f<=(x%t));
return cnt * w;
};
vector <int> last(s.size()), mem(a.size(), s.size());
for (int i = 0; i < s.size(); ++i) {
last[i] = 0;
for (int j = 1; j < a.size(); ++j) {
if (getcnt(s[i], a[j].f) > getcnt(s[i], a[last[i]].f) || (getcnt(s[i], a[j].f) == getcnt(s[i], a[last[i]].f) && a[j].f > a[last[i]].f)) {
last[i] = j;
}
}
mem[last[i]] = min(mem[last[i]], i);
}
vector <int> dp(a.size()+1, -1);
dp[0] = (x/t+1)*w;
for (int i = 0; i < a.size(); ++i) {
int cur = 0;
int lf = -1;
for (int j = i + 1; j <= a.size(); ++j) {
if (j > i + 1) {
if (mem[j - 1] != -1) {
if (lf == -1)
lf = mem[j - 1];
else
lf = min(lf, mem[j - 1]);
}
if (lf == -1)
break;
else
cur += get(i, j - 1, lf);
}
if (dp[j] == -1) {
dp[j] = dp[i]+cur+save(j);
}
else {
dp[j] = min(dp[j], dp[i]+cur+save(j));
}
}
}
cout << (int)dp[a.size()] << endl;
}
Compilation message
coach.cpp: In lambda function:
coach.cpp:46:13: warning: unused variable 'di' [-Wunused-variable]
int di = a[i].f;
^~
coach.cpp: In lambda function:
coach.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == a.size())
~~^~~~~~~~~~~
coach.cpp: In function 'int main()':
coach.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); ++i) {
~~^~~~~~~~~~
coach.cpp:59:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < a.size(); ++j) {
~~^~~~~~~~~~
coach.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); ++i) {
~~^~~~~~~~~~
coach.cpp:71:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i + 1; j <= a.size(); ++j) {
~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
