[2304] 창고 다각형

https://www.acmicpc.net/problem/2304

2304번: 창고 다각형

가장 큰 기둥을 기준으로 왼쪽, 오른쪽으로 나눈다.

오목한 부분이 있으면 안되므로, 나누어진 두개의 공간에서는 지붕이 높아지는 경우만 고려하면 되겠다.

가장 큰 기둥이 여러개 있는 경우에는 가장 큰 기둥의 최소 인덱스와 최대 인덱스를 알고있어야 한다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, ans, s = 1234, e = 0, midVal, a[1001];

vector<int> v;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n;

    int i;

    for (i = 0; i < n; i++) {

        int x, y;

        cin >> x >> y;

        a[x] = y;

        s = min(x, s);

        e = max(x, e);

        if (midVal < y) {

            midVal = y;

            v.clear();

            v.push_back(x);

        } else if (midVal == y)

            v.push_back(x);

    }

    sort(v.begin(), v.end());

    int cur = 0;

    for (i = s; a[i] != midVal; i++) {

        cur = max(a[i], cur);

        ans += cur;

    }

    ans += (midVal * (v.back() - v.front() + 1));

    cur = 0;

    for (i = e; a[i] != midVal; i--) {

        cur = max(a[i], cur);

        ans += cur;

    }

    cout << ans;

    return 0;

}

---