Submission #82727

#	Time	Username	Problem	Language	Result	Execution time	Memory
82727		Bodo171	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	796 ms	1176 KiB

semiexpress

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=3005;
long long v[nmax],act[nmax],dp[nmax];
int n,m,k,i,j;
long long a,b,c,T,coef;
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>m>>k;
    cin>>a>>b>>c;
    cin>>T;
    for(i=1;i<=m;i++)
    {
        cin>>v[i];
    }
    k-=m;
    for(long long cnt=1;cnt<m;cnt++)
    {
        if(T-1LL*(v[cnt]-1)*b>=0)
           act[0]=(1LL*T-(v[cnt]-1)*b)/a;
        else act[0]=0;
        for(coef=1;coef<=k;coef++)
        {
            if(1LL*T-(v[cnt]-1)*b-(act[coef-1]+1)*c>=0) act[coef]=act[coef-1]+(1LL*T-(v[cnt]-1)*b-(act[coef-1]+1)*c)/a+1;
            else act[coef]=act[coef-1];
            act[coef]=min(act[coef],v[cnt+1]-v[cnt]);
        }
        act[0]=min(act[0],v[cnt+1]-v[cnt]);
        for(coef=0;coef<=k;coef++)
           if(act[coef]<v[cnt+1]-v[cnt]&&T-1LL*(v[cnt]-1)*b>=0)
            act[coef]++;

        for(i=k;i>=0;i--)
            for(j=0;j<=i;j++)
               dp[i]=max(dp[i],dp[i-j]+act[j]);
    }
    long long  cnt=m;
    if(T-1LL*(v[cnt]-1)*b>=0)
        dp[k]++;
    cout<<dp[k]-1;//vezi ultima statie
    return 0;
}

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