백준 14240 (C++) 부분 수열의 점수

최초 업로드: 2025-11-06 01:56:57

최근 수정 시간: 2025-11-06 01:56:57

게시자: rlatjwls3333

카테고리: 백준

# [Diamond V] 부분 수열의 점수

[문제 링크](https://www.acmicpc.net/problem/14240)

## 문제 설명

수열 s = s1, s2, ..., sn의 점수는 Σi·si로 구할 수 있다.

수열 s의 연속된 부분 수열의 점수의 최댓값을 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 n (1 ≤ n ≤ 200,000)이 주어진다.

둘째 줄에는 s1, s2, ..., sn이 주어진다. (|si| ≤ 107)

## 출력

첫째 줄에 수열 s의 연속된 부분 수열의 점수 중 최댓값을 출력한다.

## 풀이
$(j<i)$인 j에 대해 $max(preMult[i]-preMult[j])-j(preSum[i]-preSum[j])$라는 식을 도출해 낼 수 있다. 이 식을 $-j * preSum[i] + j*preSum[j]-preMult[j] + preMult[i]$으로 정리가 가능하고 x를 $-preSum[i]$로 두면 CHT가 가능하다.

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

typedef long long ll;
const int MAX = 200'001;

ll s[MAX], preSum[MAX], preMult[MAX];

struct element {
    ll a, b;
    double x=-1e150;
};

double meetX(element a, element b) {
    return (double)(a.b-b.b)/(b.a-a.a);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=1;i<=n;i++) {
 cin >> s[i];
 preSum[i] += preSum[i-1] + s[i];
 preMult[i] = preMult[i-1] + s[i]*i;
 }

ll res=0;
 vector<element> stk;
 for(int i=1;i<=n;i++) {
 ll x = -preSum[i];
 element cur = {(i-1), (i-1)*preSum[i-1]-preMult[i-1]};
 while(!stk.empty()) {
 cur.x = meetX(cur, stk.back());
 if(cur.x>stk.back().x) break;
 stk.pop_back();
 }
 stk.push_back(cur);

int left=0, right=stk.size()-1;
 while(left<right) {
 int mid = left+right+1>>1;
 if(x<stk[mid].x) right=mid-1;
 else left=mid;
 }
 res = max(res, stk[left].a*x+stk[left].b + preMult[i]);
 }
 cout << res;
}
```