Submission #170513

#	Time	Username	Problem	Language	Result	Execution time	Memory
170513		mdn2002	Kas (COCI17_kas)	C++14	100 / 100	1262 ms	391928 KiB

kas

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,a[503],dp[500][200000],al;
int f(int x,int sum)
{
    if(x==n)
    {
        if(sum==1e5)return 0;
        else return -1e5;
    }
    if(dp[x][sum]!=-1)return dp[x][sum];
    int num=-1e5;
    num=max(num,f(x+1,sum+a[x])+a[x]);
    num=max(num,f(x+1,sum-a[x]));
    num=max(num,f(x+1,sum));
    return dp[x][sum]=num;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("lemonade.in","r",stdin);
    //freopen("lemonade.out","w",stdout);
    memset(dp,-1,sizeof dp);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        al+=a[i];
    }
    cout<<f(0,1e5)+((al-(f(0,1e5)*2)));
}

• 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