#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long lld;
const int MX=3010, inf=2e9;
lld n, m, k, a, b, c, t;
lld S[MX];
lld nxt[MX][MX], D[MX][MX];
lld E[MX][MX];
bool done[MX][MX];
void init(){
for(int i=1; i<m; i++){
lld prv=S[i], t0=t-b*S[i]+b;
for(int j=0; j<=k; j++){
lld up = (t0-c*(prv-S[i]));
nxt[i][j] = prv + (up>=0 ? up/a+1 : 0);
nxt[i][j] = max(nxt[i][j], S[i]+1);
prv=nxt[i][j];
//cout<<prv<<' ';
}
//cout<<'\n';
}
for(int i=0; i<=k; i++) D[1][i]=-inf, done[1][i]=true;
D[1][0]=0;
for(int i=0; i<=k; i++) E[1][i]=-inf, done[1][i]=true;
E[1][0]=0;
}
lld d(int i, int j){
lld &res=E[i][j];
if(done[i][j]>0) return res;
done[i][j]=true;
for(int l=0; l<=j; l++){
lld now = d(i-1, j-l) + S[i]-S[i-1]-1 - max(0LL, S[i]-1-nxt[i-1][l]+1);
now += (b*(S[i]-1)<=t ? 1 : 0);
res=max(res, now);
}
return res;
}
void solve(int u, int s, int e, int l, int r){
if(s>e) return;
lld m=(s+e)/2, pos=l, &mx=D[u][m]; mx=-inf;
for(int x=l; x<=r && x<=m; x++){
lld now=D[u-1][m-x] + S[u]-S[u-1]-1 - max(0LL, S[u]-1 - nxt[u-1][x] +1);
now += (b*(S[u]-1)<=t ? 1 : 0);
if(mx<now) pos=x, mx=now;
}
solve(u,s,m-1,l,pos);
solve(u,m+1,e,pos,r);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>m>>k>>a>>b>>c>>t; k-=m;
for(int i=1; i<=m; i++){
cin>>S[i];
}
init();
for(int i=2; i<=m; i++){
solve(i,0,k,0,k);
}
lld ans=D[m][k];
cout<<ans;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1184 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1184 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1184 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1216 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1216 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1184 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1184 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1216 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1216 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1216 KB |
Output is correct |
| 19 |
Correct |
41 ms |
23024 KB |
Output is correct |
| 20 |
Correct |
82 ms |
34552 KB |
Output is correct |
| 21 |
Correct |
9 ms |
34552 KB |
Output is correct |
| 22 |
Correct |
19 ms |
34552 KB |
Output is correct |
| 23 |
Correct |
88 ms |
34552 KB |
Output is correct |
| 24 |
Correct |
10 ms |
34552 KB |
Output is correct |
| 25 |
Correct |
8 ms |
34552 KB |
Output is correct |
| 26 |
Correct |
13 ms |
34552 KB |
Output is correct |
| 27 |
Correct |
10 ms |
34552 KB |
Output is correct |
| 28 |
Correct |
11 ms |
34552 KB |
Output is correct |
| 29 |
Correct |
26 ms |
34552 KB |
Output is correct |
| 30 |
Correct |
16 ms |
34552 KB |
Output is correct |
