Submission #182407

#	Time	Username	Problem	Language	Result	Execution time	Memory
182407		XmtosX	Kas (COCI17_kas)	C++17	100 / 100	1317 ms	395000 KiB

kas

#include <bits/stdc++.h>
using namespace std;
const int N=504;
int n,memo[N][200005],a[N];
int dp (int pos,int cur)
{
    if (pos==n)
    {
        if (cur==1e5)
            return 0;
        return 1e9;
    }
    int &ret=memo[pos][cur];
    if (ret!=-1)
        return ret;
    ret=dp(pos+1,cur)+a[pos];
    ret=min(ret,dp(pos+1,cur-a[pos]));
    ret=min(ret,dp(pos+1,cur+a[pos]));
    return ret;
}
int main()
{
    int sum=0;
    cin >>n;
    for (int i=0;i<n;i++)
        cin >>a[i],sum+=a[i];
    memset(memo,-1,sizeof memo);
    int ans= dp(0,1e5);
    cout <<ans+ (sum-ans)/2;
    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