글 읽기 - 혹시 어느 부분에서 반례가 있는지 찾아주실수 있으신가요..?

(追記) (追記ここまで)

혹시 어느 부분에서 반례가 있는지 찾아주실수 있으신가요..?

1208번 - 부분수열의 합 2

bgjun0204 2년 전 0

질문글에 올라온 다른분들의 테스트케이스 예시들은 전부 올바르게 나옵니다

카운트는 음수 -400만부터 400만까지 사용했으며, 기존의 가짓수에서 하나하나 추가하고 TableAfter배열에 기록한 후, 이후에 Table배열에 고대로 반영했습니다

반복문을 400만 * N(40)번 진행해도 문제는 없지만, 불필요한 배열 탐방을 줄이기 위해 List를 사용해 실제로 가짓수가 있는 곳만 찾아가 갱신했습니다

#include <stdio.h>
#define MAX_N 40
#define MAX_M MAX_N * 100000
int n, a[MAX_N + 1], List[MAX_M * 2 + 1], lList;
long long Table[MAX_M * 2 + 1], TableAfter[MAX_M * 2 + 1];
int main(void)
{
	int s, i, j;
	scanf("%d%d", &n, &s);
	for (i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (i = 1; i <= n; i++)
	{
		for (j = lList; j >= 1; j--)
		{
			if (Table[a[i] + List[j] + MAX_M] == 0) List[++lList] = a[i] + List[j];
			TableAfter[a[i] + List[j] + MAX_M] += Table[List[j] + MAX_M];
		}
		if (Table[a[i] + MAX_M] == 0) List[++lList] = a[i];
		TableAfter[a[i] + MAX_M]++;
		for (j = lList; j >= 1; j--) Table[List[j] + MAX_M] += TableAfter[List[j] + MAX_M], TableAfter[List[j] + MAX_M] = 0;
	}
	printf("%lld", Table[s + MAX_M]);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC