글 읽기 - 왜 맞았는 지 모르겠습니다.

dohyeokkim 8년 전 0

dc함수에서 st + 2 == ed 일 때 dat[st] + dat[st + 1] 을 고려하지 않았는데 맞았네요.

이런 거 data 부족인가요?

#include <cstdio>
#include <algorithm>
#include <climits>

using namespace std;

int dat[100000];

int dc(int st, int ed){
  if (st + 1 == ed) 
    return dat[st];

  if (st + 2 == ed) 
    return max(dat[st], dat[st + 1]);

  int mid = (st + ed) / 2;
  int res_l = dc(st, mid);
  int res_r = dc(mid, ed);
  int acc_ml = 0, acc_mr = 0, res_ml = INT_MIN, res_mr = INT_MIN;

  for (int i = mid - 1; i >= st; i--){
    acc_ml += dat[i];
    res_ml = max(res_ml, acc_ml);
  }

  for (int i = mid; i < ed; i++){
    acc_mr += dat[i];
    res_mr = max(res_mr, acc_mr);
  }

  return max({res_l, res_r, res_ml + res_mr});
}

int main(){
  int n;

  scanf("%d", &n);

  for (int i = 0; i < n; i++){
    scanf("%d", &dat[i]);
  }

  printf("%d", dc(0, n));

  return 0;
}

baekjoon 8년 전 0

ㄴㅔ 데이터 추가합니다.

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

문제

문제

출처

ICPC

왜 맞았는 지 모르겠습니다.

dohyeokkim 8년 전 0

baekjoon 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말