글 읽기 - 데이터 추가 요청

myungwoo 1년 전 0

코드에 반례가 있는데 AC가 나와서 데이터 추가 요청합니다.

[s, e] 구간에 대해 분할 정복할 때에,

m=(s+e)/2인 경우 [m, m+1] 구간에 대해 갱신을 해주지 않았습니다.

즉, 분할정복 과정 중 [m, m+1]가 답이 되는 경우 올바른 답을 구하지 못합니다.

틀린 코드 첨부합니다.

#include <bits/stdc++.h>
using namespace std;

using lld = long long;

constexpr int MAXN = 100005;
int N;
int A[MAXN];

lld dnc(int s, int e)
{
	if (s == e) return (lld)A[s]*A[s];
	int m = s+e >> 1;
	lld ret = max(dnc(s, m), dnc(m+1, e));
	lld sum = A[m]+A[m+1]; int mn = min(A[m], A[m+1]), l = m, r = m+1;
	while (l > s || r < e){
		if (r == e || l > s && A[l-1] > A[r+1]){
			sum += A[--l]; mn = min(mn, A[l]);
		}else{
			sum += A[++r]; mn = min(mn, A[r]);
		}
		ret = max(ret, sum*mn);
	}
	return ret;
}

int main()
{
	scanf("%d", &N);
	for (int i=1;i<=N;i++) scanf("%d", A+i);
	printf("%lld\n", dnc(1, N));
}

/*
반례:
4
1 999 999 1

정답:
1996002

출력:
998001
*/

startlink 1년 전 1

재채점했습니다.

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

문제

문제

출처

ICPC

데이터 추가 요청

myungwoo 1년 전 0

startlink 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말