백준 14180 (C++) 배열의 특징

최초 업로드: 2025-11-05 23:49:20

최근 수정 시간: 2025-11-05 23:49:20

게시자: rlatjwls3333

카테고리: 백준

# [Diamond V] 배열의 특징

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

## 문제 설명

길이가 N인 정수 배열 A가 주어진다. 배열의 특징 C는 ΣAi·i (1 ≤ i ≤ n) 으로 정의된다.

배열에서 수 하나를 고른 다음, 아무 위치로 이동시킬 수 있다. 이때, 배열의 시작이나 끝으로도 옮길 수 있으며, 원래 위치로도 옮길 수 있다.

배열 A에서 수를 하나만 이동시켰을 때, 배열의 특징 C의 최댓값을 구하는 프로그램을 작성하시오.

## 입력

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

둘째 줄에는 Ai (|Ai| ≤ 1,000,000)가 주어진다.

## 출력

배열에서 수를 하나만 움직인 후의 C의 최댓값을 출력한다.

## 풀이
- i 인덱스에 있는 수를 j≤i인 j까지 옮기고 나머지를 오른쪽으로 민다면 점수는 $preSum[i-1]-preSum[j-1] - (i-j)A_i$만큼 변하고 이를 정리하면 $jA_i-preSum[j-1] + preSum[i-1]-iA_i$가 되어 x를 A_i로 두면 CHT를 사용할 수 있습니다.
- 반대로 i 인덱스에 있는 수를 i≤j인 j 위치까지 옮기고 나머지를 왼쪽으로 민다면 점수는 $-(preSum[j]-preSum[i]) + (j-i)A_i$만큼 변하고 이를 정리하면 $jA_i-preSum[j] + preSum[i]-iA_i$가 되어 x를 -A_i로 두면 CHT를 사용할 수 있습니다.

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

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

ll A[MAX], preSum[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 >> A[i];
 preSum[i] = preSum[i-1]+A[i];
 }

ll res=0;
 vector<element> stk;
 for(int i=1;i<=n;i++) {
 ll x = A[i];
 element cur = {i, -preSum[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 + preSum[i-1]-i*A[i]);
 }

stk.clear();
    for(int i=n;i>=1;i--) {
        ll x = -A[i];
        element cur = {-i, -preSum[i]};

while(!stk.empty()) {
            cur.x = meetX(cur, stk.back());
            if(cur.x>stk.back().x) break;
            stk.pop_back();
        }
        stk.push_back(cur);