Submission #994141

#	Time	Username	Problem	Language	Result	Execution time	Memory
994141		vjudge1	Kas (COCI17_kas)	C++17	0 / 100	47 ms	6668 KiB

kas

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

const int N = 505;
const int S = 1e5 + 10;
int n, a[N];
bitset<N> B[S];
bool dp[S];

int main(){
    cin >> n;
    int total = 0;
    for (int i = 0; i < n; i ++)
        cin >> a[i], total += a[i];
    sort(a, a + n);

    dp[0] = 1;
    int mx = 0;
    for (int i = 0; i < n; i ++){
        for (int sm = total; sm >= a[i]; sm--){
            if (!dp[sm - a[i]]) continue;
            if (dp[sm]){
                bitset<N> b = B[sm - a[i]];
                b[i] = 1;
                b &= B[sm];
                if (!(b.any()))
                    mx = max(mx, sm);
            }
            else{
                dp[sm] = 1;
                B[sm] = B[sm - a[i]];
                B[sm][i] = 1;
            }
        }
    }

    cout << total - mx << endl;
}

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