제출 #899683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899683		aykhn	수열 (APIO14_sequence)	C++17	50 / 100	100 ms	7800 KiB

sequence

#include <bits/stdc++.h>

// author: aykhn

using namespace std;
typedef long long ll;

#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define ins insert
#define int ll
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount

const int MXN = 1e3 + 5;

int n, k;
int a[MXN], pref[MXN];
int dp[MXN][MXN];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> k;
    k++;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) dp[i][1] = pref[i] * (pref[n] - pref[i]);
    for (int i = 1; i <= n; i++)
    {
        for (int j = i - 1; j >= 1; j--)
        {
            for (int k1 = 2; k1 <= k; k1++)
            {
                dp[i][k1] = max(dp[i][k1], dp[j][k1 - 1] + (pref[i] - pref[j]) * (pref[n] - pref[i]));
            }
        }
    }
    cout << dp[n][k] << '\n';
    int x = n;
    int y = k;
    vector<int> v;
    while (y > 1)
    {
        for (int i = x - 1; i >= 1; i--)
        {
            if (dp[x][y] == dp[i][y - 1] + (pref[x] - pref[i]) * (pref[n] - pref[x]))
            {
                x = i;
                break;
            }
        }
        y--;
        v.pb(x);
    }
    sort(all(v));
    for (int x : v) cout << x << ' ';
    cout << '\n';
}

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