제출 #1024018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024018		kustizus	Kas (COCI17_kas)	C++17	100 / 100	85 ms	1256 KiB

kas

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen ("file.inp","r",stdin);
    // freopen ("file.out","w",stdout);
    int n, a, sum = 0;
    cin >> n;
    vector<int> dp(1e5 + 5, -1), bef(1e5 + 5, -1);
    bef[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a;
        sum += a;
        for (int j = 0; j <= 1e5; j++)
            if (bef[j] != -1)
            {
                if (j + a <= 1e5)
                    dp[j + a] = max(dp[j + a], bef[j]);
                if (j >= a)
                    dp[j - a] = max(dp[j - a], bef[j] + a);
                else
                    dp[a - j] = max(dp[a - j], bef[j] + j);
            }
        for (int j = 0; j <= 1e5; j++)
        {
            bef[j] = max(dp[j], bef[j]);
            dp[j] = -1;
        }
    }
    cout << sum - bef[0];
    return 0;
}

• 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: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10