Submission #363759

#	Time	Username	Problem	Language	Result	Execution time	Memory
363759		BartolM	Split the sequence (APIO14_sequence)	C++17	28 / 100	223 ms	5484 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1005;
const int K=202;

int n, k;
ll dp[N][K];
ll pref[N];
int bac[N][K];

void solve() {
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=k; ++j) {
            for (int l=0; l<i; ++l) {
                ll curr=dp[l][j-1]+pref[l]*(pref[i]-pref[l]);
                if (curr>dp[i][j]) dp[i][j]=curr, bac[i][j]=l;
            }
        }
    }
    printf("%lld\n", dp[n][k]);
    pii pp=mp(n, k);
    while (pp.Y) {
        pp.X=bac[pp.X][pp.Y--];
        printf("%d ", pp.X);
    }
}

void load() {
    scanf("%d %d", &n, &k);
    for (int i=1; i<=n; ++i) {
        scanf("%lld", &pref[i]);
        pref[i]+=pref[i-1];
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void load()':
sequence.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         scanf("%lld", &pref[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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