답안 #100241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100241 2019-03-10T03:09:19 Z luciocf Kas (COCI17_kas) C++14
100 / 100
692 ms 200184 KB
#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";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 199928 KB Output is correct
2 Correct 159 ms 199972 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 199972 KB Output is correct
2 Correct 169 ms 199896 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 199984 KB Output is correct
2 Correct 181 ms 199960 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 200004 KB Output is correct
2 Correct 166 ms 200004 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 200064 KB Output is correct
2 Correct 163 ms 200028 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 199940 KB Output is correct
2 Correct 171 ms 200184 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 199896 KB Output is correct
2 Correct 165 ms 199928 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 286 ms 200092 KB Output is correct
2 Correct 208 ms 200080 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 199984 KB Output is correct
2 Correct 381 ms 200116 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 528 ms 199980 KB Output is correct
2 Correct 692 ms 200056 KB Output is correct