#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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
176 ms |
199928 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
142 ms |
199932 KB |
Output is correct |
2 |
Incorrect |
149 ms |
199992 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
140 ms |
199892 KB |
Output is correct |
2 |
Incorrect |
154 ms |
199928 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
147 ms |
200112 KB |
Output is correct |
2 |
Correct |
143 ms |
199988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
147 ms |
199948 KB |
Output is correct |
2 |
Correct |
141 ms |
199928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
141 ms |
199928 KB |
Output is correct |
2 |
Correct |
167 ms |
199952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
173 ms |
200056 KB |
Output is correct |
2 |
Correct |
186 ms |
199888 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
219 ms |
199944 KB |
Output is correct |
2 |
Correct |
171 ms |
200152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
214 ms |
200012 KB |
Output is correct |
2 |
Correct |
278 ms |
199920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
334 ms |
200016 KB |
Output is correct |
2 |
Correct |
509 ms |
200100 KB |
Output is correct |