#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
const ll SIZE = 1e6 * 2 + 10, INF = 1e9 * 1e9 + 10;
vector<ll> vec;
ll dpAns[10000][2], dpt[SIZE], good[SIZE];
ll n, m, k, a, b, c;
void add(int curInd, int us, int s) {
for (int i = k; i >= 0; i--) {
if (i - us >= 0) {
dpAns[i][curInd] = max(dpAns[i][curInd], dpAns[i - us][curInd] + s);
}
}
}
int main()
{
fastInp;
cin >> n >> m >> k;
cin >> a >> b >> c;
ll t;
cin >> t;
vec.resize(m);
for (auto &cur : vec) cin >> cur;
ll ans = 0;
vector<ll> addt;
for (int i = 0; i < vec.size(); i++) {
int lastInd = vec[i], lastIndT = (vec[i] - 1) * b;
for (int j = 0; j < k; j++) {
if (lastIndT > t) break;
ll l = lastInd, r = n + 1;
if (i < vec.size() - 1 && lastInd >= vec[i + 1]) break;
while (r - l > 1) {
ll mid = (l + r) / 2;
if (lastIndT + (mid - lastInd) * a > t) {
r = mid;
}
else {
l = mid;
}
}
if (l == lastInd) {
if (j != 0) {
addt.push_back(1);
}
else ans++;
l++;
lastIndT += (l - lastInd) * c;
continue;
}
if (i < vec.size() - 1 && l >= vec[i + 1]) {
if (j != 0) {
addt.push_back(vec[i + 1] - lastInd);
}
else ans += vec[i + 1] - lastInd;
break;
}
l++;
lastIndT += (l - lastInd) * c;
if (j != 0) {
addt.push_back(l - lastInd);
}
else ans += l - lastInd;
lastInd = l;
}
}
k -= m;
/*good[1] = 1;
ll lastI = -1, curInd = 0;
for (int i = 1; i <= n; i++) {
dpt[i] = dpt[i - 1] + a;
if (vec[lastI + 1] == i) {
good[i] = 1;
if (i == 1) {
dpt[i] = 0;
lastI++;
continue;
}
dpt[i] = min(dpt[i], min(dpt[vec[lastI]] + c * (i - vec[lastI]), dpt[vec[lastI]] + b * (i - vec[lastI])));
lastI++;
}
}
ll ans = 0, added = 0, lastPos = 1, s = 0;
for (int i = 1; i <= n; i++) {
if (dpt[i] <= t) {
ans++;
}
else {
s++;
}
dpt[i] = min(dpt[i], dpt[i - 1] + a);
if (dpt[i] > t || good[i]) {
if (dpt[i] > t) s--;
addt.push_back(s);
if (dpt[i] > t) s++;
}
if (dpt[i] > t) {
added = 1;
s = 1;
dpt[i] = dpt[lastPos] + c * (i - lastPos);
lastPos = i;
}
if (dpt[i] > t) {
s = 0;
continue;
}
if (good[i]) {
lastPos = i;
curInd = !curInd;
for (int j = 0; j <= k; j++) dpAns[j][curInd] = dpAns[j][!curInd];
s = 0;
added = 0;
}
}*/
sort(addt.rbegin(), addt.rend());
for (int i = 0; i < min(ull(addt.size()), ull(k)); i++) {
add(0, 1, addt[i]);
}
ll s;
s = 0;
for (int i = 0; i <= k; i++) s = max(s, dpAns[i][0]);
cout << ans + s - 1;
return 0;
}
/*
10 3 5
10 3 5
30
1
6
10
10 3 5
10 3 5
25
1
6
10
90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90
12 3 4
10 1 2
30
1
11
12
300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300
1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000
*/
Compilation message
semiexpress.cpp: In function 'int main()':
semiexpress.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0; i < vec.size(); i++) {
| ~~^~~~~~~~~~~~
semiexpress.cpp:57:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if (i < vec.size() - 1 && lastInd >= vec[i + 1]) break;
| ~~^~~~~~~~~~~~~~~~
semiexpress.cpp:77:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if (i < vec.size() - 1 && l >= vec[i + 1]) {
| ~~^~~~~~~~~~~~~~~~
semiexpress.cpp:150:20: warning: comparison of integer expressions of different signedness: 'int' and 'const long long unsigned int' [-Wsign-compare]
150 | for (int i = 0; i < min(ull(addt.size()), ull(k)); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
