https://www.acmicpc.net/problem/4384


후 이거 22501 스캔 다 안하고 링크드리스트랑

vector로 버퍼 두개해서 유효한값만 딱딱하고 지나가게끔 최적화 하려고 그랬는데

한 line 200 넘어가고 머리 너무 터질거 같아서 떄려침

걍 링크드리스트랑 버퍼 포기하고 나머지 최적화했음


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
 
int weight[101];
bool cash[51][22501] = { false };
int listindex[51];
int half;
int n;
 
int main()
{
    int sum = 0;
    int ans = 0;
 
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &weight[i]);
        sum += weight[i];
    }
 
    half = (sum / 2);
 
    int hap = 0;
    cash[0][0] = true;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < ((i < (n / 2 + n % 2)) ? i : (n / 2 + n % 2)); j++)
        {
            if ((n - i + 1 + j) < n / 2)
            {
                continue;
            }
            for (int k = 0; k <= ((hap<half)?hap:half); k++)
            {
                if (cash[j][k])
                {
                    if (k + weight[i] <= half)
                    {
                        cash[j + 1][k + weight[i]] = true;
                        if ((j + 1 == n / 2) || (j + 1 == (n / 2 + n % 2)))
                        {
                            if (ans < k + weight[i])
                            {
                                ans = k + weight[i];
                            }
                        }
                    }
                }
            }
        }
        hap += weight[i];
    }
 
    printf("%d %d ", ans, sum - ans);
    
    return 0;
}
cs




지금 코드포스 div2 콘테스트 곧함 ㄱㄱ하좌