#include<bits/stdc++.h>
using namespace std;
const int SM = 1001;
bool dp[2][SM][SM];
int main()
{
int n;
cin >> n;
int a[1 + n];
int x = 0;
for(int i = 1; i <= n; ++i)
{
cin >> a[i];
x += a[i];
}
dp[0][0][0] = true;
for(int i = 1; i <= n; i ++)
{
bool b = i & 1, nb = !b;
for(int j = 0; j <= x; j++)
for(int k = 0; k <= x; k++)
{
dp[b][j][k] = dp[nb][j][k];
if(j >= a[i])
dp[b][j][k] |= dp[nb][j - a[i]][k];
if(k >= a[i])
dp[b][j][k] |= dp[nb][j][k - a[i]];
}
}
int mx = 0;
for(int i = 0; i <= x; i++)
if(dp[n & 1][i][i])
mx = i;
cout << mx + (x - 2 * mx) << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
2140 KB |
Output is correct |
2 |
Correct |
12 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
2388 KB |
Output is correct |
2 |
Correct |
12 ms |
2140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
2140 KB |
Output is correct |
2 |
Correct |
13 ms |
2392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
2140 KB |
Output is correct |
2 |
Correct |
15 ms |
2388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
2140 KB |
Output is correct |
2 |
Correct |
14 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
2136 KB |
Output is correct |
2 |
Correct |
41 ms |
2140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
2140 KB |
Output is correct |
2 |
Correct |
56 ms |
2364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
119 ms |
2384 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
94 ms |
2528 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
94 ms |
2384 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |