Submission #1166913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166913		sunflower	Kas (COCI17_kas)	C++17	70 / 100	106 ms	51520 KiB

kas

#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 debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#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 numNotes;

#define MAX_NOTES 505
int cost[MAX_NOTES + 2];

namespace subtask1 {
    bool check() {
        return (numNotes <= 13);
    }

    int rem, answer;

    int arr[MAX_NOTES + 2];

    int lt(int a, int n) {
        int res = 1;
        for (; n > 0; n >>= 1, a *= a)
            if (n & 1) res *= a;
        return res;
    }

    void process() {
        FOR(mask, 0, lt(3, numNotes) - 1) {
            int temp = mask;
            FOR(i, 0, numNotes - 1) {
                arr[i] = temp % 3;
                temp /= 3;
            }

            int A = 0, B = 0, sum = 0;
            FOR(j, 0, numNotes - 1) {
                if (arr[j] == 1) A += cost[j + 1];
                else if (arr[j] == 2) B += cost[j + 1];
                sum += cost[j + 1];
            }

            if (A == B && minimize(rem, sum - A - B)) answer = sum - A;
        }
    }

    void solve() {
        rem = int(1e9), answer = 0;
        process();
        cout << answer;
    }
};

namespace subtask2 {
    bool check() {
        return (numNotes <= 50 && accumulate(cost + 1, cost + 1 + numNotes, 0) <= 1000);
    }

    bool dp[52][1002][1002];

    void solve() {
        memset(dp, false, sizeof(dp));

        int sum = accumulate(cost + 1, cost + 1 + numNotes, 0);
        dp[0][0][0] = true;
        FOR(i, 1, numNotes) {
            FORD(j, sum, 0)
                FORD(k, sum, 0) {
                    // ko use;
                    dp[i][j][k] = dp[i - 1][j][k];

                    // use;
                    if (j >= cost[i]) dp[i][j][k] |= dp[i - 1][j - cost[i]][k];
                    if (k >= cost[i]) dp[i][j][k] |= dp[i - 1][j][k - cost[i]];
                }
        }

        int ans = 0;
        FOR(i, 0, sum) if (dp[numNotes][i][i]) {
            ans = sum - i;
        }
        cout << ans;
    }
};

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    // freopen("test.inp","r",stdin);
    // freopen("test.out","w",stdout);
    cin >> numNotes;
    FOR(i, 1, numNotes) cin >> cost[i];

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

    return 0;
}

/* Discipline - Calm */

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10