Submission #1369563

#TimeUsernameProblemLanguageResultExecution timeMemory
1369563domiCandy (EGOI23_candy)C++20
100 / 100
52 ms8120 KiB
#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "Yes" << endl; return; }
#define NO { cout << "No" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 1e2;
const int INV_MAX = 1e4;

using namespace std;

int dp[NMAX + 5][INV_MAX + 5], a[NMAX + 5], n, f, t;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> f >> t;

    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];

        for (int taken = f; taken >= 1; --taken) {
            for (int swaps = i - taken; swaps <= n * n; ++swaps)
                dp[taken][swaps] = max(dp[taken][swaps], dp[taken - 1][swaps - (i - taken)] + a[i]);
        }

    }

    for (int swaps = 0; swaps <= n * n; ++swaps) {
        if (dp[f][swaps] >= t) {
            cout << swaps << '\n';
            exit(0);
        }
    }
    cout << "NO\n";
    return 0;
}
/*
    dp[taken][swaps] = suma maxima pe prefixul de marime taken daca am facut swaps interschimbari intre elemente vecine
*/
#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...