#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
const int SMX = 3e3+5;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int dp[SMX][SMX];
int cost[SMX][SMX];
void dnc(int k, int l, int r, int L, int R)//answer for all l, r lies between L and R.
{
if(l > r)
return;
int m = (l+r)/2;
in bet = {-INF, -INF};
for(int opt = L; opt <= min(R, m); opt++)
bet = max(bet, {dp[k-1][m-opt]+cost[k][opt], opt});
dp[k][m] = bet.f; int opt = bet.s;
dnc(k, l, m-1, L, opt);
dnc(k, m+1, r, opt, R);
return;
}
signed main()
{
fast();
int n, m, k, a, b, c, T;
cin >> n >> m >> k >> a >> b >> c >> T;
vector<int> v;
v.pb(0);
for(int i = 1; i <= m; i++)
{
int x; cin >> x;
v.pb(x);
}
v.pb(n+1);
for(int i = 1; i <= m; i++)
{
int t = b*(v[i]-1);
int loc = v[i];
if(t > T)
break;
int prev = 0;
for(int n = 0; n <= k; n++)
{
if(loc >= v[i+1])
{
cost[i][n] = prev;
continue;
}
if(t > T)
{
cost[i][n] = prev;
continue;
}
int ell = (T-t)/a;
//t, t+a, t+2a, .., t + ell a
//loc, loc+1, .., loc + ell
ell = min(ell, v[i+1]-1-loc);
cost[i][n] = prev + (ell+1);
t+=((ell+1)*c);
loc+=(ell+1);
prev = cost[i][n];
}
}
/*for(int i = 1; i <= m; i++)
{
printf("For the %dth gap between %d and %d: ", i, v[i], v[i+1]);
cout << "\n";
for(int j = 0; j <= k; j++)
cout << cost[i][j] << " ";
cout << endl;
}*/
for(int i = 1; i <= m; i++)
{
dnc(i, 0, k, 0, k);
/*for(int j = 0; j <= k; j++)
{
in ok = {-INF, -INF};
for(int r = 0; r <= j; r++)
ok = max(ok, {dp[i-1][j-r]+cost[i][r], r});
dp[i][j] = ok.f;
//cout << "r: " << ok.s << " j-r : " << j-ok.s << endl;
}*/
//cout << "----------------" << endl;
}
cout << dp[m][k-m]-1;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2396 KB |
Output is correct |
15 |
Correct |
1 ms |
2396 KB |
Output is correct |
16 |
Correct |
1 ms |
2652 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2396 KB |
Output is correct |
15 |
Correct |
1 ms |
2396 KB |
Output is correct |
16 |
Correct |
1 ms |
2652 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
2652 KB |
Output is correct |
19 |
Correct |
59 ms |
42656 KB |
Output is correct |
20 |
Correct |
43 ms |
40784 KB |
Output is correct |
21 |
Correct |
25 ms |
36180 KB |
Output is correct |
22 |
Correct |
41 ms |
44624 KB |
Output is correct |
23 |
Correct |
74 ms |
81748 KB |
Output is correct |
24 |
Correct |
29 ms |
58780 KB |
Output is correct |
25 |
Correct |
17 ms |
23896 KB |
Output is correct |
26 |
Correct |
59 ms |
92948 KB |
Output is correct |
27 |
Correct |
47 ms |
73248 KB |
Output is correct |
28 |
Correct |
51 ms |
75344 KB |
Output is correct |
29 |
Correct |
16 ms |
25944 KB |
Output is correct |
30 |
Correct |
6 ms |
7772 KB |
Output is correct |