Submission #107885

#	Time	Username	Problem	Language	Result	Execution time	Memory
107885		SamAnd	수열 (APIO14_sequence)	C++17	22 / 100	2053 ms	65452 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
const int N = 202;
const long long INF = 1000000009000000009;

int n, m;
int a[N];
long long p[N];

long long dp[N][N][N];
int pp[N][N][N];
int pk[N][N][N];

void tp(int l, int r, int k)
{
    if (k == 0)
        return;
    cout << pp[l][r][k] << endl;
    tp(l, pp[l][r][k], pk[l][r][k]);
    tp(pp[l][r][k] + 1, r, k - 1 - pk[l][r][k]);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        p[i] = p[i - 1] + a[i];

    for (int d = 1; d <= n; ++d)
    {
        for (int l = 1; l <= n - d + 1; ++l)
        {
            int r = l + d - 1;
            for (int k = 1; k <= m; ++k)
            {
                dp[l][r][k] = -INF;
            }
        }
    }

    for (int d = 1; d <= n; ++d)
    {
        for (int l = 1; l <= n - d + 1; ++l)
        {
            int r = l + d - 1;
            for (int k = 1; k <= min(m, d - 1); ++k)
            {
                for (int i = l; i < r; ++i)
                {
                    for (int kk = 0; kk <= k - 1; ++kk)
                    {
                        if ((p[i] - p[l - 1]) * (p[r] - p[i]) + dp[l][i][kk] + dp[i + 1][r][k - 1 - kk] > dp[l][r][k])
                        {
                            dp[l][r][k] = (p[i] - p[l - 1]) * (p[r] - p[i]) + dp[l][i][kk] + dp[i + 1][r][k - 1 - kk];
                            pp[l][r][k] = i;
                            pk[l][r][k] = kk;
                        }
                    }
                }
            }
        }
    }
    cout << dp[1][n][m] << endl;
    tp(1, n, m);
    return 0;
}

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