Submission #100241

#	Time	Username	Problem	Language	Result	Execution time	Memory
100241		luciocf	Kas (COCI17_kas)	C++14	100 / 100	692 ms	200184 KiB

kas

#include <bits/stdc++.h>

using namespace std;

const int maxn = 510;
const int maxm = 1e5+10;
const int inf = 1e9+10;

int num[maxn], n;

int dp[maxn][maxm];

int solve(int pos, int soma)
{
	if (pos == n+1 && !soma) return 0;
	if (pos == n+1) return -inf;
	if (dp[pos][soma] != -1) return dp[pos][soma];

	int caso1 = num[pos]+solve(pos+1, soma+num[pos]);
	int caso2 = solve(pos+1, soma-num[pos]);
	int caso3 = solve(pos+1, soma);

	return dp[pos][soma] = max({caso1, caso2, caso3});
}

int main(void)
{
	int soma = 0;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> num[i];
		soma += num[i];
	}

	memset(dp, -1, sizeof dp);

	cout << soma-solve(1, 0) << "\n";
}

• 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