제출 #1368856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368856		norrawichzzz	수열 (APIO14_sequence)	C++20	71 / 100	217 ms	196608 KiB

sequence

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

#define int long long

const long long INF = 1e18;

const int N = 1e5+5, K=201;
long long dp[K][N], par[K][N], a[N], p[N];

int n,k;

void dac(int k, int l, int r, int optl, int optr) {
    if (l>r) return;

    long long optval = -1;
    int optk = -1;

    int mid=(l+r)/2;

    for (int i=optl; i<min(mid, optr+1); i++) {
        long long val = dp[k-1][i] + (p[mid]-p[i])*(p[n]-p[mid]);
        if (val >= optval) {
            optk = i;   
            optval = val;
        }
    }
    dp[k][mid] = optval;
    par[k][mid] = optk;
    
    dac(k, l, mid-1, optl, optk);
    dac(k, mid+1, r, optk, optr);
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>> n>> k;

    for (int i=1; i<=n; i++) cin>> a[i], p[i] = p[i-1]+a[i];

    for (int i=1; i<=n; i++) dp[0][i] = -1;

    for (int t=1; t<=k; t++) {
        dac(t,1, n, 0, n);
    }

    long long ans = -1;
    int id = n, cur=k;
    for (int i=1; i<n; i++) {
        if (ans <= dp[k][i]) {
            ans = dp[k][i];
            id = i;
        }
    }

    vector<int> pos;

    while (cur>0) {
        int idx = par[cur][id];
        pos.push_back(id);
        id = idx;
        cur--;
    }   
    reverse(pos.begin(), pos.end());

    cout<< ans<< '\n';
    for (auto &x : pos) cout<< x<< ' ';
}

• 서브태스크 1: 11 / 11
• 서브태스크 2: 11 / 11
• 서브태스크 3: 11 / 11
• 서브태스크 4: 17 / 17
• 서브태스크 5: 21 / 21
• 서브태스크 6: 0 / 29