Submission #1354448

#TimeUsernameProblemLanguageResultExecution timeMemory
1354448yyc000123Candy (EGOI23_candy)C++20
19 / 100
63 ms15312 KiB
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int N = 105 ;
int n , f , arr[N] , pos , ans = 0x3f3f3f3f ;
ll t , dp[2][N][N*N] ;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;
    cin >> n >> f >> t ;
    for(int i=1 ; i<=n ; i++) cin >> arr[i] ;
    if(n==1){
        if(arr[1]>=t) cout << "0\n" ;
        else cout << "NO\n" ;
        return 0 ;
    }
    for(int i=1 ; i<=f ; i++){
        for(int j=n+1 ; j>f ; j--){
            for(int l=0 ; l<=n*n ; l++){
                dp[pos][j][l]=max(dp[!pos][j][l]+arr[i],dp[pos][j+1][l]) ;
                if(l) dp[pos][j][l]=max(dp[pos][j][l],dp[pos][j][l-1]) ;
                if(l-(j-i)>=0) dp[pos][j][l]=max(dp[pos][j][l],dp[!pos][j+1][l-(j-i)]+arr[j]) ;
            }
        }
        pos = !pos ;
    }
    for(int i=1 ; i<=n ; i++){
        for(int j=0 ; j<=n*n ; j++){
            if(dp[!pos][i][j]>=t) ans=min(ans,j) ;
        }
    }
    if(ans==0x3f3f3f3f) cout << "NO\n" ;
    else cout << ans << '\n' ;
    return 0 ;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...