제출 #373270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373270		flappybird	수열 (APIO14_sequence)	C++14	71 / 100	2084 ms	83064 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define MAX 101010
#define ln '\n'
lld arr[MAX], dp[MAX], p[MAX], s[MAX], ans[MAX];
int path[MAX][202];
void f(lld ind, lld l, lld r, lld low, lld high) {
    if (l > r || low > high) return;
    lld i, mid = (l + r) / 2, mini = mid - 1;
    dp[mid] = 0;
    for (i = max(low, ind - 1); i <= min(high, mid - 1); i++) {
        if (dp[mid] < p[i] + s[i] * (s[mid] - s[i])) {
            dp[mid] = p[i] + s[i] * (s[mid] - s[i]);
            mini = i;
        }
    }
    path[mid][ind] = (int)mini;
    f(ind, l, mid - 1, low, mini);
    f(ind, mid + 1, r, mini, high);
}
int main(void) {
    ios::sync_with_stdio(0), cin.tie(0);
    lld N, K;
    cin >> N >> K;
    lld i;
    for (i = 1; i <= N; i++) {
        cin >> arr[i];
        s[i] = arr[i] + s[i - 1];
    }
    int j;
    for (i = 2; i <= K + 1; i++) {
        f(i, 1, N, 1, N);
        for (j = 1; j <= N; j++) {
            p[j] = dp[j];
        }
    }
    cout << dp[N] << ln;
    for (i = K + 1; i >= 2; i--) {
        ans[i] = (lld)path[N][i];
        N = (lld)path[N][i];
    }
    for (i = 2; i <= K + 1; i++) cout << ans[i] << ln;
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29