제출 #1369563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369563		domi	Candy (EGOI23_candy)	C++20	100 / 100	52 ms	8120 KiB

Main

#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
*/

• 서브태스크 0: 0 / 0
• 서브태스크 1: 6 / 6
• 서브태스크 2: 19 / 19
• 서브태스크 3: 16 / 16
• 서브태스크 4: 30 / 30
• 서브태스크 5: 29 / 29