글 읽기 - 결과가 왜 달라질까요

hy01n 3년 전 0

17번 줄을

return H[s]*H[s] 에서

return (sum[s]-sum[s-1])*H[s] 로 고치면

맞았습니다라고 뜨긴 하는데

sum[s]-sum[s-1] = H[s] 아닌가요

왜 결과가 달라지는지 모르겠습니다.

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> H;
vector<long long> sum;

long long func(int s, int e)
{
	if(s==e)
	{
		return 0;
	}
	if(s+1==e)
	{
		return (H[s]*H[s]);
	}
	
	int mid = (s+e)/2;
	long long result = max(func(s,mid),func(mid,e));
	
	int h=H[mid], l=mid, r=mid;
	while(r-l+1<e-s)
	{
		int p = s<l?min(h,H[l-1]):-1;
		int q = r<e-1?min(h,H[r+1]):-1;
		if(p>=q)
		{
			h=p;
			l--;
		}
		else
		{
			h=q;
			r++;
		}
		result = max((long long)result,(sum[r]-sum[l-1])*h);
	}
	
	return result;
}


int main()
{
	
	cin>>N;
	H.assign(N+1,0);
	sum.assign(N+1,0);
	long long s=0;
	for(int i=1;i<=N;i++)
	{
		cin>>H[i];
		s+=H[i];
		sum[i]=s;
	}
	
	cout<<func(1,N+1)<<endl;
	return 0;
}

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

문제

문제

출처

ICPC

결과가 왜 달라질까요

hy01n 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말