Submission #51006

#	Time	Username	Problem	Language	Result	Execution time	Memory
51006		Diuven	Semiexpress (JOI17_semiexpress)	C++11	100 / 100	88 ms	34552 KiB

semiexpress

#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;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52