제출 #1131609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131609		sunflower	Holding (COCI20_holding)	C++17	88 / 110	149 ms	106284 KiB

holding

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int N, L, R, money;

const int inf = (int) 1e9 + 7;
const long long INF = (long long) 1e18 + 7;

#define MAX_N 102
int a[MAX_N + 2];

namespace subtask1 {
    bool check() {
        return (N <= 13 && R == N);
    }

    void solve() {
        ll ans = 0;
        FOR(i, L, R) ans += 1LL * a[i];

        ll sumCostBase = ans;

        FOR(mask, 0,  MASK(N) - 1) {
            int numBit = __builtin_popcount(mask);
            if (numBit & 1) continue;

            int sumIdPrev = 0, sumCostPrev = 0;
            int sumIdCur  = 0, sumCostCur  = 0;

            int numIdPrev = 0;
            FOR(i, 0, N - 1) if (BIT(mask, i)) {
                int id = i + 1;
                if (id < L) {
                    ++numIdPrev;
                    sumIdPrev += id;
                    sumCostPrev += 1LL * a[id];
                } else {
                    sumIdCur += id;
                    sumCostCur += 1LL * a[id];
                }
            }

            if (numIdPrev != numBit / 2) continue;

            if (sumIdCur - sumIdPrev <= money)
                minimize(ans, sumCostBase + sumCostPrev - sumCostCur);
        }

        cout << ans;
    }
}

namespace subtask3 {
    bool check() {
        return (N <= 50);
    }

    int dp[52][10'002][52];
    // debug;
    // chua can toi 10'000; ma ~ n^2 ma thoi;

    void solve() {
        memset(dp, 0x3f, sizeof(dp));

        dp[L - 1][0][0] = 0;
        a[0] = inf;
        FOR(i, L, R) { // N <=> R;
            FOR(prevUse, 0, money) {
                FOR(nxtID, 0, N) {
                    if (L <= nxtID && nxtID <= R) continue;

                    // khong lam gi ca;
                    minimize(dp[i][prevUse][nxtID], dp[i - 1][prevUse][nxtID] + a[i]);

                    // co lam;
                    FOR(prevID, 0, nxtID - 1) {
                        if (L <= prevID && prevID <= R) continue;

                        if (prevUse + abs(i - nxtID) <= money) {
                            minimize(dp[i][prevUse + abs(i - nxtID)][nxtID], dp[i - 1][prevUse][prevID] + a[nxtID]);
                        }
                    }
                }
            }
        }

        ll ans = 0;
        FOR(i, L, R) ans += 1LL * a[i];

        FOR(use, 0, money) FOR(id, 0, N) {
            minimize(ans, dp[R][use][id]);
        }

        cout << ans;
    }
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
//    freopen("holding.inp","r",stdin);
//    freopen("holding.out","w",stdout);
    cin >> N >> L >> R >> money;
    FOR(i, 1, N) cin >> a[i];

//    if (subtask1 :: check()) return subtask1 :: solve(), 0;
    if (subtask3 :: check()) return subtask3 :: solve(), 0;

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 0 / 22