Submission #100176

#	Time	Username	Problem	Language	Result	Execution time	Memory
100176		sofhiasouza	Kas (COCI17_kas)	C++14	70 / 100	509 ms	200152 KiB

kas

#include <bits/stdc++.h>
#define MAXN 510
#define inf 0x3f3f3f3f
using namespace std;

int n, vet[MAXN], dp[MAXN][100010], sum = 0, sa[MAXN];

inline int func(int u, int s1)
{
	if(u == n+1 and s1 != 0) return inf;
	if(u == n+1) return 0;
	if(dp[u][s1] != -1) return dp[u][s1];

	int p1 = func(u+1, s1+vet[u]);
	int p2 = inf;
	if(vet[u] <= s1) p2 = func(u+1, s1-vet[u]);
	int p3 = func(u+1, s1);
	if(p3 != inf) p3 += vet[u];

	int menor = min({p1, p2, p3});

	if(s1 == 0) menor = min(menor, sum-sa[u-1]);
	return dp[u][s1] = menor;
}

int main()
{
	cin >> n;
	memset(dp, -1, sizeof dp);
	sa[0] = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> vet[i];
		sum += vet[i];
		sa[i] = sa[i-1]+vet[i];
	}
	int result = func(1, 0);
	cout << (sum-result)/2 + result << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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