백준14180 배열의 특징

작성일 | In

문제 링크

  • http://icpc.me/14180

사용 알고리즘

  • CHT

풀이

각 원소가 오른쪽으로 이동하는 경우와 왼쪽으로 이동하는 경우를 나누어서 값의 변화를 정리해보면 CHT스러운 식이 나오게 됩니다.
CHT를 해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
const ll inf = 1e18;

class CHT {
public:
	bool isInc;
	CHT(bool _isInc) {
		isInc = _isInc;
	}
	deque<p> line; // slope, y-intersect
	double inter(int i, int j) { // 직선 line[i], line[j]의 교점의 x좌표
		return 1.00*(line[i].Y - line[j].Y) / (line[j].X - line[i].X);
	}
	ll funcval(ll i, ll x) {
		return line[i].X*x + line[i].Y;
	}
	void pushline(ll a, ll b) {
		line.push_back({ a,b });
		int i = line.size() - 1;
		while (i > 1 && inter(i, i - 1) < inter(i - 1, i - 2)) { // double
			line[i - 1] = line.back();
			line.pop_back();
			i--;
		}
	}
	int binsearch(ll k) { // 점 k가 올라타는 직선의 index
		int st = 0;
		int en = line.size() - 1;
		while (st < en) {
			int mid = (st + en) / 2;
			if (k < inter(mid, mid + 1)) en = mid; // double
			else st = mid + 1;
		}
		return en;
	}
	ll findval(ll k) {
		if (isInc) {
			if (line.empty()) return 1e18; // 정상적이라면 발생하지 않을 상황		
			while (line.size() > 1 && funcval(0, k) > funcval(1, k)) {
				line.pop_front();
			}
			return funcval(0, k);
		}
		if (line.empty()) return 1e18; // 정상적이라면 발생하지 않을 상황
		if (line.size() == 1) return funcval(0, k);
		return funcval(binsearch(k), k);
	}
};

ll arr[202020], sum[202020];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        cin >> arr[i]; arr[i] = -arr[i]; sum[i] = sum[i-1] + arr[i];
    }

    CHT cht1(0);
	cht1.pushline(-1, 0);
	ll mn = 9e18;
	for(int i=2; i<=n; i++) {
		ll val = cht1.findval(-arr[i]) + sum[i-1] - i * arr[i];
		if (mn > val) mn = val;
		cht1.pushline(-i, -sum[i - 1]);
	}
	CHT cht2(0);
	cht2.pushline(n, -sum[n]);
	for (int i = n-1; i>=1; i--) {
		ll val = cht2.findval(arr[i]) + sum[i] - i * arr[i];
		if (mn > val) mn = val;
		cht2.pushline(i, -sum[i]);
	}
    if(mn > 0) mn = 0;
    ll s = mn;
    for(int i=1; i<=n; i++) s += i * arr[i];
    //if(mx < 0) mx = 0;
    cout << -s;
}