【題解】ZeroJudge d890: 3.禮物分配(gift)

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int n, k;
    while (cin >> n >> k){
        int gifts[n], total = 0;
        for (int i = 0; i < n; i++){
            cin >> gifts[i];
            total += gifts[i];
        }
        int half = total/2;
        int dp[half+1];
        memset(dp, 0, sizeof(dp));
        
        for (int i = 0; i < n; i++){
            for (int j = half; j >= gifts[i]; j--){
                if (gifts[i] + dp[j-gifts[i]] > dp[j]){
                    dp[j] = gifts[i] + dp[j-gifts[i]];
                }
            }
        }
        cout << dp[half] << " " << total - dp[half] << "\n";
    }
}

import sys
lines = sys.stdin.readlines()

n, k = map(int, lines[0].split())
gifts = [int(line) for line in lines[1:]]
total = sum(gifts)
    
half = total // 2
dp = [0 for _ in range(half+1)]
for i in range(n):
    for j in range(half, gifts[i]-1, -1):
        if (gifts[i] + dp[j - gifts[i]] > dp[j]):
            dp[j] = gifts[i] + dp[j - gifts[i]]
            
print(dp[half], total - dp[half])