Submission #1354852

#TimeUsernameProblemLanguageResultExecution timeMemory
1354852sallyCandy (EGOI23_candy)C++20
100 / 100
479 ms768128 KiB
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int mx = 100;
#define int long long
int N, F, T;
vector<int> num;
int dp[mx+2][mx+2][mx*mx+2];
signed main() {
    cin>>N>>F>>T;
    num.push_back(0);
    for(int i=1; i<=N; i++) {
        int c; cin>>c;
        num.push_back(c);
    }
    vector<int> temp = num;
    sort(temp.begin(), temp.end(), greater<long long>());
    int sum = 0;
    for(int i=0; i<F; i++) sum+=temp[i];
    if(sum<T) {
        cout<<"NO";
        return 0;
    }
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=F; j++) {
            for(int k=0; k<=N*N; k++) {
                dp[i][j][k] = max({dp[i][j][k], dp[i-1][j][k], (k-(i-j)>=0 ? dp[i-1][j-1][k-(i-j)] + num[i] : 0LL)});
            }   
        }
    }
    int ans = N*N+10;
    for(int i=0; i<=N*N; i++) {
        if(dp[N][F][i]>=T) {ans = i; break;}
    }
    cout<<ans;
}   
#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...