Submission #1266295

#TimeUsernameProblemLanguageResultExecution timeMemory
1266295meisgoodSemiexpress (JOI17_semiexpress)C++20
0 / 100
29 ms70976 KiB
#include <bits/stdc++.h>
using namespace std ;
#define int long long
int S[3003] ;
int dp[3003][3003] ;
signed main(){
  int N,M,K,i,j ;
  cin >> N >> M >> K ;
  int A,B,C ;
  cin >> A >> B >> C ;
  int T ;
  cin >> T ;
  for (i = 1 ; i <= M ; i ++) cin >> S[i] ;
  for (i = 0 ; i < 3003 ; i ++) for (j = 0 ; j < 3003 ; j ++) dp[i][j]=-INT_MAX/2 ;
  dp[1][0]=1 ;
  for (i = 2 ; i <= M ; i ++){
    vector <int> cann(K+3,-INT_MAX/2) ;
    for (j = 0 ; j <= min(K,S[i]-S[i-1]-1) ; j ++){
      int nnd=(S[i-1])*B ;
      int can=1 ;
      if ((T-nnd)/C<j){
        can+=(T-nnd)/C ;
      }
      else {
        can+=j ;
        can+=(T-nnd-C*j)/A ;
      }
      can=min(can,S[i]-S[i-1]-1) ;
      cann[j]=can ;
      // cout << cann[j] << " " ;
    }
    // cout << endl ;
    for (j = 0 ; j <= K ; j ++){
      for (int k = 0 ; k <= j ; k ++){
        dp[i][j]=max(dp[i][j],dp[i-1][j-k]+cann[k]) ;
      }
    }
  }
  cout << dp[M][K] << endl ;
	return 0 ;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...