oj.uz

답안 #82727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
82727 2018-11-01T13:29:55 Z Bodo171 Semiexpress (JOI17_semiexpress) C++14
100 / 100
 796 ms 1176 KB 
#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.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 3 ms 696 KB Output is correct
10 Correct 2 ms 808 KB Output is correct
11 Correct 3 ms 940 KB Output is correct
12 Correct 2 ms 940 KB Output is correct
13 Correct 2 ms 940 KB Output is correct
14 Correct 2 ms 940 KB Output is correct
15 Correct 2 ms 940 KB Output is correct
16 Correct 2 ms 940 KB Output is correct
17 Correct 2 ms 940 KB Output is correct
18 Correct 3 ms 940 KB Output is correct

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 3 ms 696 KB Output is correct
10 Correct 2 ms 808 KB Output is correct
11 Correct 3 ms 940 KB Output is correct
12 Correct 2 ms 940 KB Output is correct
13 Correct 2 ms 940 KB Output is correct
14 Correct 2 ms 940 KB Output is correct
15 Correct 2 ms 940 KB Output is correct
16 Correct 2 ms 940 KB Output is correct
17 Correct 2 ms 940 KB Output is correct
18 Correct 3 ms 940 KB Output is correct
19 Correct 162 ms 956 KB Output is correct
20 Correct 796 ms 984 KB Output is correct
21 Correct 3 ms 984 KB Output is correct
22 Correct 14 ms 1000 KB Output is correct
23 Correct 417 ms 1064 KB Output is correct
24 Correct 3 ms 1064 KB Output is correct
25 Correct 2 ms 1064 KB Output is correct
26 Correct 3 ms 1076 KB Output is correct
27 Correct 3 ms 1112 KB Output is correct
28 Correct 3 ms 1128 KB Output is correct
29 Correct 105 ms 1144 KB Output is correct
30 Correct 193 ms 1176 KB Output is correct