Submission #1329591

#TimeUsernameProblemLanguageResultExecution timeMemory
1329591the_ZHERSemiexpress (JOI17_semiexpress)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define int unsigned long long
#define boost ios_base::sync_with_stdio(0);cin.tie(0);
const int inf=1e18;
const int N=2e5+100;
const int N1=1e5+5;
const int mod=1e9+7;
const int k1=sqrt(N1);
using namespace std;
int dp[3005][3005];
int dp1[3005][3005];
int v[N];
signed main(){
    boost;
    int n,m,k;
    cin>>n>>m>>k;
    int a,b,c;
    cin>>a>>b>>c;
    int t;
    cin>>t;
    int ans=0;
    for(int i=1;i<=m;i++){
        cin>>v[i];
        if((v[i]-1)*b<=t){
            ans++;
        }
    }
    int cnt=k-m;
    int cnt1=0;
    for(int i=1;i<m;i++){
        int l=v[i];
        int r=v[i+1]-1;
        if(l==r){
            continue;
        }
        cnt1=(v[i]-1)*b;
        if(cnt1>t){
            break;
        }
        int l1=l;
        int cnt2=cnt1;
        int l2=l;
        int cnt4=0;
        for(int j=0;j<=cnt;j++){
            int cnt3=t-cnt2;
            if(cnt3<0){
                break;
            }
            cnt3/=a;
            cnt3=min(cnt3,r-l1);
            l1=min(l1+cnt3,r);
            int x=0;
            if(j>0){
                x=dp[i][j-1];
            }
            dp[i][j]=cnt3+x+cnt4;
            if(l1==r){
                for(int p=j+1;p<=cnt;p++){
                    dp[i][p]=r-l;
                }
                break;
            }
            l1++;
            cnt4=1;
            cnt2=((l1-l)*c)+cnt1;
            if(cnt2>t){
                break;
            }
            if(l1==r){
                for(int p=j+1;p<=cnt;p++){
                    dp[i][p]=r-l;
                }
                break;
            }
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<=cnt;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"\n";
    int mx=0;
    for(int i=1;i<m;i++){
        for(int j=0;j<=k-m;j++){
            for(int l=j;l<=k-m;l++){
                dp1[i][j]=max(dp1[i][j],dp[i][j]+dp1[i-1][l-j]);
            }
            mx=max(mx,dp1[i][j]);
        }
    }
    cout<<ans-1+mx;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...