#pragma region
#pragma optimize("O3")
#include <bits/stdc++.h>
#define Weakoying ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pqueue priority_queue
#define pb push_back
#define F first
#define S second
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define cmax(a, b) a = (a > b ? a : b)
#define cmin(a, b) a = (a < b ? a : b)
#define put(x) cout << x << endl;
#define putarr(x) for(int i = 0; i < sizeof(x); i++) cout << x[i] << (" \n")[i == sizeof(x) - 1];
#define stop system("pause");
#define MEM(x, n) memset(x, n, sizeof(x));
#define lowbit(x) x &(-x)
#if !LOCAL
#define endl "\n"
#endif
const int INF = 0x3f3f3f3f;
const int P = 1e9+7;
using namespace std;
#pragma endregion
/******************************************************************************/
#define MAXN 100005
#define MAXM 3005
int n, m, k, t;
int A, B, C;
int x[MAXM];
pii dis[MAXM];
void find_dist()
{
MEM(dis, 63);
dis[1] = {0, 0};
for(int i = 1; i < m; i++)
{
dis[x[i]].F = B * (x[i] - 1);
dis[x[i]].S = 0;
}
for(int i = 2; i <= n; i++)
{
cmin(dis[i].F, A * (i - 1));
int F = upper_bound(x, x + m, i) - x;
F--;
if(F == -1) continue;
cmin(dis[i].F, dis[x[F]].F + A * (abs(x[F] - i)));
cmin(dis[i].S, abs(x[F] - i));
}
// for(int i = 1; i <= n; i++)
// cout << dis[i].F << " ";
// cout << endl;
// for(int i = 1; i <= n; i++)
// cout << dis[i].S << " ";
// cout << endl;
}
void sol()
{
cin >> n >> m >> k;
cin >> A >> B >> C;
cin >> t;
set<int> s;
for(int i = 0; i < m; i++)
{
cin >> x[i];
}
find_dist();
// int ans = 0;
// for(int i = 2; i <= n; i++)
// {
// if(dis[i].F <= t)
// ans++;
// }
// // cout << ans << endl;
// sort(dis + 1, dis + n + 1, greater<pii>());
// for(int i = 1; dis[i].F > t && k > m && i <= n; i++)
// {
// // cout << dis[i].F << endl;
// if(dis[i].F - dis[i].S * (A - C) <= t)
// {
// ans++;
// k--;
// }
// }
// cout << ans << endl;
if(k - m == 2)
{
int ans = 0;
for(int i = 2; i < n; i++)
{
int ouo = 0;
// if(binary_search(x, x + m, i)) continue;
for(int j = i + 1; j <= n; j++)
{
// if(binary_search(x, x + m, j)) continue;
int cnt = 0;
for(int k = 2; k <= n; k++)
{
int tmp = dis[k].F;
int F = upper_bound(x, x + m, k) - x;
F--;
if(F >= 0)
{
cmin(tmp, A * (k - x[F]) + dis[x[F]].F);
}
if(upper_bound(x, x + m, i) - x - 1 != -1)
cmin(tmp, A * (abs(k - i)) + C * abs(i - (x[upper_bound(x, x + m, i) - x - 1])) + dis[x[upper_bound(x, x + m, i) - x - 1]].F);
if(upper_bound(x, x + m, j) - x - 1 != -1)
cmin(tmp, A * (abs(k - j)) + C * abs(j - (x[upper_bound(x, x + m, j) - x - 1])) + dis[x[upper_bound(x, x + m, j) - x - 1]].F);
if(tmp <= t)
cnt++;
// cout << tmp << " ";
}
// cout << endl;
// if(cnt > ans)
// cout << i << " " << j << endl;
cmax(ans, cnt);
}
// cout << i << " " << ouo << endl;
}
cout << ans << endl;
}
}
signed main()
{
Weakoying;
int t = 1;
//while (cin >> t)
{
while (t--)
{
sol();
}
}
return 0;
}
Compilation message
semiexpress.cpp:1: warning: ignoring '#pragma region ' [-Wunknown-pragmas]
1 | #pragma region
|
semiexpress.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
2 | #pragma optimize("O3")
|
semiexpress.cpp:29: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
29 | #pragma endregion
|
semiexpress.cpp: In function 'void find_dist()':
semiexpress.cpp:20:41: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
20 | #define MEM(x, n) memset(x, n, sizeof(x));
| ^
semiexpress.cpp:40:2: note: in expansion of macro 'MEM'
40 | MEM(dis, 63);
| ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from semiexpress.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
211 | struct pair
| ^~~~
semiexpress.cpp: In function 'void sol()':
semiexpress.cpp:98:8: warning: unused variable 'ouo' [-Wunused-variable]
98 | int ouo = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
305 ms |
360 KB |
Output is correct |
| 2 |
Incorrect |
342 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
305 ms |
360 KB |
Output is correct |
| 2 |
Incorrect |
342 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
305 ms |
360 KB |
Output is correct |
| 2 |
Incorrect |
342 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
