제출 #1339910

#제출 시각아이디문제언어결과실행 시간메모리
1339910lxz20071231Candy (EGOI23_candy)C++20
100 / 100
218 ms23584 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long; using db = double; using i128 = __int128_t;
template <class T> using v = vector<T>;
using pii = pair<int, int>; using vi = v<int>; using vpi = v<pii>; using vvi = v<vi>; using vvpi = v<vpi>;
using pll = pair<ll, ll>; using vll = v<ll>; using vpl = v<pll>; using vvl = v<vll>; using vvpl = v<vpl>;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()

const int INF = 1e9;
const ll INFLL = 1e18;

int n, k; ll T;
ll a[101];

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n >> k >> T;
    for (int i=1; i<=n; i++){
        cin >> a[i];
    }

    int ms = n*(n-1);
    vvl dp1 = vvl(k+1, vll(ms+1, 0)), dp2 = vvl(k+1, vll(ms+1, 0));

    for (int i=n; i>0; i--){
        swap(dp1, dp2);
        dp1 = vvl(k+1, vll(ms+1, 0));
        for (int j=1; j<=k; j++){
            for (int sw = 0; sw<=ms; sw++){
                dp1[j][sw] = a[i] + dp2[j-1][sw];
                if (j <= sw){
                    dp1[j][sw] = max(dp1[j][sw], dp2[j][sw-j]);
                }
            }
        }
    }

    for (int i=0; i<=ms; i++){
        if (dp1[k][i] >= T){
            cout << i << '\n';
            return 0;
        }
    }

    cout << "NO\n";
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...