RiseOJ는 solved.ac와 제휴 관계가 없습니다. 티어 아이콘 © solved.ac. solved.ac
포럼
A00007

알파카컵 1회: G - 알파카 목장의 겨울 준비

Diamond V 다이아몬드 V
난이도
2s
시간 제한
2048MB
메모리 제한
1
맞았습니다!!
7
제출 수
14.3%
정답률
레이팅

의견: 1

설명

알파카 목장에는 일렬로 놓인 \(N\)개의 우리가 있다.
\(i\)번째 우리에는 \(A_i\)마리의 알파카가 있다.
\(A_i < 0\)이라면 그 우리에는 추위를 좋아하는 알파카가 \(-A_i\)마리 있으며, 난방 만족도 계산에서 음수로 기여한다는 뜻이다.

겨울이 오기 전에, 목장 주인은 정확히 \(K\)개의 연속한 구간을 골라 난방 장치를 설치하려고 한다.

하나의 난방 장치는 연속한 우리 몇 개를 덮을 수 있다.
단, 서로 다른 난방 장치가 덮는 구간은 서로 겹치면 안 된다.
또한 선택하는 각 구간은 적어도 하나의 우리를 포함해야 한다.

구간 \([l, r]\)에 난방 장치를 설치했을 때 얻는 만족도는 다음과 같다.

$$ [A_l + A_{l+1} + \dots + A_r]^2 $$

목장 주인은 정확히 \(K\)개의 서로 겹치지 않는 연속 구간을 골라 만족도의 총합을 최대화하려고 한다.

이론적으로 가능한 만족도의 최댓값을 구하시오.

단, 선택한 연속 구간이 목장 전체를 덮지 않아도 된다.

제약

\(1 \le N \le 100{,}000\)
\(1 \le K \le \min(30, N)\)
\(-10{,}000 \le A_i \le 10{,}000\)
정답은 \(2^{60}\) 이하임이 보장된다.

입력 형식

첫째 줄에 두 정수 \(N\), \(K\)가 주어진다.

둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \dots, A_N\)이 주어진다.

출력 형식

정확히 \(K\)개의 서로 겹치지 않는 연속 구간을 골랐을 때 얻을 수 있는 만족도의 최댓값을 출력한다.
답은 \(2^{60}\) 이하임이 보장된다.

서브태스크
서브태스크점수설명

서브태스크 1

1점

주어진 예제만 채점한다.

서브태스크 2

7점

\(N \le 8\), \(K \le 2\)

서브태스크 3

10점

모든 \(i\)에 대하여 \(A_i \ge 0\)

서브태스크 4

12점

\(K = 2\)

서브태스크 5

12점

\(K = 3\)

서브태스크 6

18점

\(N \le 1000\), \(K \le 15\)

서브태스크 7

40점

추가 제한 없음

예제 1
입력
5 2
3 -2 4 -1 2
출력
34
예제 2
입력
5 2
2 -5 3 -4 1
출력
41
예제 3
입력
6 3
4 -1 -2 6 -3 2
출력
62
문제 정보

cute_alpaca 작성

출처 알파카컵 1회

대회 > 알파카컵 > 알파카컵 1회
태그
#컨벡스 헐 트릭 JudgeOriginal

해설

알파카컵 1회: G - 알파카 목장의 겨울 준비

알파카컵 1회: G - 알파카 목장의 겨울 준비

1. 문제 요약

일렬로 놓인 \(N\)개의 우리에 각각 \(A_i\)마리의 알파카가 있습니다. (\(A_i\)는 음수일 수 있습니다.) 서로 겹치지 않는 정확히 \(K\)개의 비어 있지 않은 연속 구간 \([l_1, r_1], [l_2, r_2], \dots, [l_K, r_K]\)를 고를 때, 각 구간의 만족도는 그 구간의 합의 제곱 \(\left(\sum_{t=l}^{r} A_t\right)^2\)으로 정의됩니다. 이 만족도의 총합을 최대화하는 것이 목표입니다.

접두사 합 \(\text{pre}[i] = A_1 + A_2 + \dots + A_i\) (단, \(\text{pre}[0] = 0\))를 정의하면, 구간 \([l+1, r]\)의 합은 \(\text{pre}[r] - \text{pre}[l]\)이고, 그 만족도는 \((\text{pre}[r] - \text{pre}[l])^2\)이 됩니다. 이 형태가 풀이의 출발점입니다.

2. [서브태스크 1]: 주어진 예제만 채점한다.

정해의 일부분이라도 올바르게 구현했는지, 혹은 입출력 형식을 정확히 맞추었는지 확인하기 위한 서브태스크입니다. 입력으로 주어지는 예제 세 개에 대해서만 올바른 답을 출력하면 점수를 얻습니다.

  • 풀이: 어떤 방법을 사용하든 무방합니다. 작은 예제이므로 아래 서브태스크 2의 완전 탐색만으로도 충분히 정답을 얻을 수 있습니다. 입출력 형식(\(N\), \(K\)를 읽고 \(A\) 배열을 읽어 정수 하나를 출력)만 정확히 지키면 됩니다.

  • 시간 복잡도: 예제의 크기가 매우 작으므로 어떤 풀이든 즉시 통과합니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
ll n, k, a[10];
ll best = LLONG_MIN;
void rec(ll pos, ll cnt, ll cur) {
    if (cnt == k) { best = max(best, cur); return; }
    if (n - pos < k - cnt) return;
    for (ll s = pos; s < n; s++) {
        ll sum = 0;
        for (ll e = s; e < n; e++) {
            sum += a[e];
            rec(e + 1, cnt + 1, cur + sum * sum);
        }
    }
}
int main() {
    fastio
    cin >> n >> k;
    for (ll i = 0; i < n; i++) cin >> a[i];
    rec(0, 0, 0);
    cout << best << endl;
    return 0;
}

3. [서브태스크 2]: \(N \le 8\), \(K \le 2\)

\(N\)이 최대 8이고 고르는 구간의 개수 \(K\)도 최대 2로 매우 작은 조건입니다. 가능한 모든 경우의 수를 직접 따져 보아도 시간 내에 충분히 끝납니다.

  • 풀이: 첫 구간의 시작점과 끝점을 모두 시도하고, 그 다음 칸부터 두 번째 구간의 시작점과 끝점을 다시 모두 시도하는 완전 탐색을 수행합니다. 각 단계에서 선택한 구간 합의 제곱을 누적하고, 정확히 \(K\)개를 골랐을 때의 누적값으로 정답 후보를 갱신합니다. 남은 칸 수가 아직 고르지 못한 구간 수보다 적으면 가지치기하여 탐색을 끊습니다.

  • 시간 복잡도: 구간 하나를 고르는 경우의 수가 \(O(N^2)\)이고 이를 \(K\)번 중첩하므로 \(O(N^{2K})\)입니다. \(N \le 8\), \(K \le 2\)에서는 \(8^4 \approx 4096\) 수준으로 매우 여유롭습니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
ll n, k, a[10];
ll best = LLONG_MIN;
void rec(ll pos, ll cnt, ll cur) {
    if (cnt == k) { best = max(best, cur); return; }
    if (n - pos < k - cnt) return;          // 남은 칸이 부족하면 가지치기
    for (ll s = pos; s < n; s++) {          // 다음 구간의 시작점
        ll sum = 0;
        for (ll e = s; e < n; e++) {        // 다음 구간의 끝점
            sum += a[e];
            rec(e + 1, cnt + 1, cur + sum * sum);
        }
    }
}
int main() {
    fastio
    cin >> n >> k;
    for (ll i = 0; i < n; i++) cin >> a[i];
    rec(0, 0, 0);
    cout << best << endl;
    return 0;
}

4. [서브태스크 3]: 모든 \(i\)에 대하여 \(A_i \ge 0\)

모든 원소가 음이 아닌 경우입니다. 음수가 없다는 사실은 문제의 구조를 단순화하는 강력한 단서입니다.

  • 풀이: 모든 \(A_i \ge 0\)이면 접두사 합 \(\text{pre}\)가 단조 증가합니다. 어떤 구간을 더 길게 늘여도 그 합은 절대 줄지 않으므로, 구간을 쪼개는 것보다 한 덩어리로 합치는 쪽이 (혹은 양 끝을 더 키우는 쪽이) 항상 유리합니다. 이런 단조 구조에서도 일반적인 구간 분할 최적화를 그대로 적용할 수 있도록, 이후 서브태스크에서 쓰는 구간 분할 DP를 그대로 사용하면 됩니다. 즉 \(\text{dp}[j][i]\)를 "앞에서부터 \(i\)개의 원소를 보았을 때 \(j\)개의 구간을 골라 얻는 최댓값"으로 정의하고, \(i\)번째 원소를 어느 구간에도 넣지 않거나, \(i\)에서 끝나는 구간을 새로 시작하는 두 경우로 전이합니다. 음수가 없으므로 모든 부분합의 제곱이 음이 아니어서 별도의 예외 처리 없이 DP가 자연스럽게 최적을 찾습니다.

  • 시간 복잡도: 아래 일반 DP를 그대로 쓰면 \(O(N^2 \cdot K)\)입니다. 이 서브태스크의 작은 입력에서는 충분히 통과합니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
const ll NEG = LLONG_MIN / 4;
ll n, k, a[1005], pre[1005], dp[16][1005];
int main() {
    fastio
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; }
    for (ll i = 0; i <= n; i++) dp[0][i] = 0;
    for (ll j = 1; j <= k; j++) for (ll i = 0; i <= n; i++) dp[j][i] = NEG;
    for (ll j = 1; j <= k; j++) {
        for (ll i = 1; i <= n; i++) {
            ll best = dp[j][i - 1];                 // i번째 원소를 쓰지 않음
            for (ll l = j - 1; l < i; l++) {        // [l+1 .. i]를 j번째 구간으로
                if (dp[j - 1][l] <= NEG) continue;
                ll d = pre[i] - pre[l];
                best = max(best, dp[j - 1][l] + d * d);
            }
            dp[j][i] = best;
        }
    }
    cout << dp[k][n] << endl;
    return 0;
}

5. [서브태스크 4]: \(K = 2\)

정확히 두 개의 구간만 고르는 경우입니다. 음수가 섞여 있으므로 단순히 "가장 큰 합 두 개"를 고른다고 끝나지 않으며, 두 구간이 서로 겹치지 않아야 한다는 제약을 다뤄야 합니다.

  • 풀이: 핵심 아이디어는 구간 분할 DP입니다. \(\text{dp}[j][i]\)를 "앞에서부터 \(i\)개의 원소만 사용해서 서로 겹치지 않는 \(j\)개의 구간을 골랐을 때의 최대 만족도"로 정의합니다. 전이는 두 가지입니다. (1) \(i\)번째 원소를 어느 구간에도 포함시키지 않으면 \(\text{dp}[j][i-1]\), (2) \(i\)에서 끝나는 새 구간 \([l+1, i]\)를 만들면 \(\text{dp}[j-1][l] + (\text{pre}[i] - \text{pre}[l])^2\)입니다. \(K = 2\)이므로 \(j\)가 1과 2 두 층만 계산하면 됩니다. 두 번째 구간은 첫 번째 구간이 끝난 지점 이후에서 시작하므로, \(l\)을 적절히 잡는 것만으로 겹치지 않음이 보장됩니다.

  • 시간 복잡도: \(\text{dp}[j][i]\) 한 칸을 채우는 데 \(l\)에 대한 \(O(N)\) 반복이 들어가므로 \(O(N^2 \cdot K)\)이며, \(K = 2\)에서는 \(O(N^2)\)입니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
const ll NEG = LLONG_MIN / 4;
ll n, k, a[1005], pre[1005], dp[16][1005];
int main() {
    fastio
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; }
    for (ll i = 0; i <= n; i++) dp[0][i] = 0;
    for (ll j = 1; j <= k; j++) for (ll i = 0; i <= n; i++) dp[j][i] = NEG;
    for (ll j = 1; j <= k; j++) {                   // K = 2 이면 j = 1, 2만 사용
        for (ll i = 1; i <= n; i++) {
            ll best = dp[j][i - 1];
            for (ll l = j - 1; l < i; l++) {
                if (dp[j - 1][l] <= NEG) continue;
                ll d = pre[i] - pre[l];
                best = max(best, dp[j - 1][l] + d * d);
            }
            dp[j][i] = best;
        }
    }
    cout << dp[k][n] << endl;
    return 0;
}

6. [서브태스크 5]: \(K = 3\)

구간을 세 개 고르는 경우입니다. \(K = 2\)에서 세운 DP가 그대로 일반화됨을 확인하는 단계입니다.

  • 풀이: 서브태스크 4의 DP를 그대로 사용하되 \(j\)를 1부터 3까지 계산하면 됩니다. \(\text{dp}[j][i]\)의 정의와 전이식이 \(K\)의 값에 전혀 의존하지 않으므로, 코드는 \(K = 2\)일 때와 완전히 동일하고 단지 \(K\)만 3으로 바뀝니다. 이로써 이 DP가 임의의 \(K\)로 확장 가능한 일반해의 골격임을 알 수 있습니다.

  • 시간 복잡도: 마찬가지로 \(O(N^2 \cdot K)\)입니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
const ll NEG = LLONG_MIN / 4;
ll n, k, a[1005], pre[1005], dp[16][1005];
int main() {
    fastio
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; }
    for (ll i = 0; i <= n; i++) dp[0][i] = 0;
    for (ll j = 1; j <= k; j++) for (ll i = 0; i <= n; i++) dp[j][i] = NEG;
    for (ll j = 1; j <= k; j++) {                   // K = 3 이면 j = 1, 2, 3
        for (ll i = 1; i <= n; i++) {
            ll best = dp[j][i - 1];
            for (ll l = j - 1; l < i; l++) {
                if (dp[j - 1][l] <= NEG) continue;
                ll d = pre[i] - pre[l];
                best = max(best, dp[j - 1][l] + d * d);
            }
            dp[j][i] = best;
        }
    }
    cout << dp[k][n] << endl;
    return 0;
}

7. [서브태스크 6]: \(N \le 1000\), \(K \le 15\)

\(N\)과 \(K\)가 적당히 작아서, 앞에서 세운 일반 구간 분할 DP를 그대로 구현하면 통과하는 구간입니다.

  • 풀이: 서브태스크 4~5에서 완성한 \(O(N^2 \cdot K)\) DP를 임의의 \(K\)에 대해 그대로 돌립니다. \(\text{dp}[j][i]\)를 채울 때 새 구간의 시작 경계 \(l\)을 \(j-1\)부터 \(i-1\)까지 모두 시도하는 이중 루프가 핵심이며, \(\text{dp}[j-1][l]\)이 아직 유효하지 않은 (\(K\)개를 채울 수 없는) 상태는 \(\text{NEG}\)로 표시해 건너뜁니다. \(N \le 1000\), \(K \le 15\)이면 연산량이 \(1000^2 \times 15 = 1.5 \times 10^7\) 수준이라 제한 시간 내에 무난히 들어옵니다.

  • 시간 복잡도: \(O(N^2 \cdot K)\). 최대 \(1.5 \times 10^7\) 연산으로 여유롭게 통과합니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
const ll NEG = LLONG_MIN / 4;
ll n, k, a[1005], pre[1005], dp[16][1005];
int main() {
    fastio
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; }
    for (ll i = 0; i <= n; i++) dp[0][i] = 0;
    for (ll j = 1; j <= k; j++) for (ll i = 0; i <= n; i++) dp[j][i] = NEG;
    for (ll j = 1; j <= k; j++) {
        for (ll i = 1; i <= n; i++) {
            ll best = dp[j][i - 1];                 // i를 쓰지 않는 경우
            for (ll l = j - 1; l < i; l++) {        // [l+1 .. i]를 j번째 구간으로
                if (dp[j - 1][l] <= NEG) continue;
                ll d = pre[i] - pre[l];
                best = max(best, dp[j - 1][l] + d * d);
            }
            dp[j][i] = best;
        }
    }
    cout << dp[k][n] << endl;
    return 0;
}

8. 정해

\(N\)이 최대 \(10^5\), \(K\)가 최대 30이므로 \(O(N^2 \cdot K)\) DP는 \(10^{10}\) 규모가 되어 시간 안에 들어오지 못합니다. DP의 골격은 그대로 두되, 안쪽 \(l\) 루프를 자료구조로 가속해야 합니다.

핵심: 제곱항을 일차식으로 분리하기

\(j\)층의 전이식은 다음과 같습니다.
$$ \text{dp}[j][i] = \max_{j-1 \le l < i} \Big(\text{dp}[j-1][l] + (\text{pre}[i] - \text{pre}[l])^2 \Big) $$
제곱을 전개하면
$$ (\text{pre}[i] - \text{pre}[l])^2 = \text{pre}[i]^2 - 2\,\text{pre}[l]\,\text{pre}[i] + \text{pre}[l]^2 $$
입니다. 여기서 \(\text{pre}[i]^2\)은 \(l\)과 무관한 공통 항이므로 \(\max\) 밖으로 뺄 수 있습니다. 그러면
$$ \text{dp}[j][i] = \text{pre}[i]^2 + \max_{j-1 \le l < i} \Big(\underbrace{(-2\,\text{pre}[l])}_{\text{기울기 } m} \cdot \underbrace{\text{pre}[i]}_{x} + \underbrace{\big(\text{dp}[j-1][l] + \text{pre}[l]^2\big)}_{\text{절편 } c} \Big) $$
가 됩니다. 즉 각 후보 \(l\)은 기울기 \(m = -2\,\text{pre}[l]\), 절편 \(c = \text{dp}[j-1][l] + \text{pre}[l]^2\)인 직선 하나에 대응하고, 우리가 구하려는 값은 \(x = \text{pre}[i]\)를 대입했을 때 여러 직선 중 최댓값입니다. 이것이 전형적인 Convex Hull Trick(CHT) / Li Chao Tree 형태입니다.

주의할 점은 \(\text{pre}[i]\)가 단조롭지 않고 (음수가 있으므로) 직선의 기울기도 단조롭지 않다는 것입니다. 따라서 "삽입·질의 모두 임의 순서"를 지원하는 자료구조가 필요하며, 여기서는 구현이 단순한 Li Chao Tree를 사용합니다. 좌표 범위는 \(|\text{pre}[i]| \le N \cdot 10^4 = 10^9\)이므로 \(x \in [-10^9, 10^9]\)로 잡습니다.

알고리즘

\(j\)를 1부터 \(K\)까지 처리합니다. 각 층마다 새로운 Li Chao Tree를 하나 만들고, \(i\)를 1부터 \(N\)까지 증가시키며 다음을 수행합니다.
1. 직선 후보로 \(l = i-1\)을 추가합니다 (단, \(l \ge j-1\)이고 \(\text{dp}[j-1][l]\)이 유효할 때). 이렇게 하면 \(i\)를 질의하는 시점에 \(l < i\)인 모든 후보가 이미 트리에 들어 있습니다.
2. \(x = \text{pre}[i]\)에서 트리의 최댓값 \(q\)를 질의하고, \(\text{dp}[j][i] = \max(\text{dp}[j][i-1],\ \text{pre}[i]^2 + q)\)로 갱신합니다.

정답은 \(\text{dp}[K][N]\)입니다.

값의 크기는 \(\text{pre}[l]^2 \le 10^{18}\), \(\text{dp} \le 2^{60} \approx 1.15 \times 10^{18}\), 기울기·\(x\) 곱 \(|m \cdot x| \le 2 \times 10^{18}\) 수준으로 모두 64비트 부호 있는 정수 범위(\(\approx 9.22 \times 10^{18}\)) 안에 들어오므로 long long으로 안전합니다. 다만 비어 있는 노드를 나타내는 음의 무한대 표식이 연산 중 넘치지 않도록 LLONG_MIN / 4로 넉넉히 잡습니다.

  • 풀이: 위 변형으로 안쪽 \(l\) 루프를 Li Chao Tree 질의 한 번(\(O(\log V)\), \(V\)는 좌표 범위)으로 대체합니다. 각 층에서 직선 \(N\)개를 한 번씩 삽입하고 \(N\)번 질의하므로 한 층이 \(O(N \log V)\), 전체는 \(O(N \cdot K \cdot \log V)\)입니다.

  • 시간 복잡도: \(O(N \cdot K \cdot \log V)\). \(N = 10^5\), \(K = 30\), \(\log V \approx 31\)에서 약 \(10^8\) 규모이며, 최댓값 입력에서도 0.8초 내외로 동작해 제한 시간 2초 안에 통과합니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
const ll NEG = LLONG_MIN / 4;
ll n, k;
ll a[100005], pre[100005], dp[31][100005];
struct Line { ll m, c; ll eval(ll x) const { return m * x + c; } };
const ll XLO = -1000000000LL, XHI = 1000000000LL;
struct LiChao {                                  // 직선의 최댓값을 관리하는 Li Chao Tree
    struct Node { Line line; int l, r; };
    vector<Node> t;
    int root;
    void init() { t.clear(); root = -1; }
    int newnode(Line ln) { t.push_back({ln, -1, -1}); return (int)t.size() - 1; }
    void insert(int node, ll lo, ll hi, Line nw) {
        ll mid = lo + (hi - lo) / 2;
        bool lef = nw.eval(lo) > t[node].line.eval(lo);
        bool md  = nw.eval(mid) > t[node].line.eval(mid);
        if (md) swap(t[node].line, nw);          // 가운데에서 더 좋은 직선을 노드에 둔다
        if (lo == hi) return;
        if (lef != md) {                         // 왼쪽 절반에서 교차
            if (t[node].l == -1) t[node].l = newnode(nw);
            else insert(t[node].l, lo, mid, nw);
        } else {                                 // 오른쪽 절반에서 교차
            if (t[node].r == -1) t[node].r = newnode(nw);
            else insert(t[node].r, mid + 1, hi, nw);
        }
    }
    ll query(int node, ll lo, ll hi, ll x) {
        if (node == -1) return NEG;
        ll res = t[node].line.eval(x);
        if (lo == hi) return res;
        ll mid = lo + (hi - lo) / 2;
        if (x <= mid) return max(res, query(t[node].l, lo, mid, x));
        else return max(res, query(t[node].r, mid + 1, hi, x));
    }
    void add(ll m, ll c) {                       // 직선 y = m*x + c 삽입
        Line ln{m, c};
        if (root == -1) root = newnode(ln);
        else insert(root, XLO, XHI, ln);
    }
    ll qry(ll x) { return query(root, XLO, XHI, x); }
};
int main() {
    fastio
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    pre[0] = 0;
    for (ll i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
    for (ll i = 0; i <= n; i++) dp[0][i] = 0;
    for (ll j = 1; j <= k; j++)
        for (ll i = 0; i <= n; i++) dp[j][i] = NEG;
    for (ll j = 1; j <= k; j++) {
        LiChao lc; lc.init();
        for (ll i = 1; i <= n; i++) {
            ll l = i - 1;                        // l < i 인 후보를 미리 삽입
            if (l >= j - 1 && dp[j - 1][l] > NEG)
                lc.add(-2 * pre[l], dp[j - 1][l] + pre[l] * pre[l]);
            ll best = dp[j][i - 1];              // i번째 원소를 쓰지 않는 경우
            ll q = lc.qry(pre[i]);               // x = pre[i] 에서 직선 최댓값
            if (q > NEG) best = max(best, pre[i] * pre[i] + q);
            dp[j][i] = best;
        }
    }
    cout << dp[k][n] << endl;
    return 0;
}

평가 및 의견

알파카컵 1회: G - 알파카 목장의 겨울 준비

개요
출제자 난이도 Diamond V 다이아몬드 V 의견 1 / 50 공개 집계 (커뮤니티 난이도, 주요 주제, 품질)는 의견이 충분히 모이면 공개됩니다.
티어 투표 분포
Diamond V 다이아몬드 V 1

Log in to rate problems.

개별 의견

풀이 제출

알파카컵 1회: G - 알파카 목장의 겨울 준비

게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다. 로그인하고 제출하기
작성 중 Rush? 언어 레퍼런스 읽기 ↗
공개
C++20 Tab 들여쓰기 · Ctrl+/ 주석 토글 · Enter 자동 들여쓰기
행1 열1 1줄 0자 공백: 4 · UTF-8