Submission #589375

#	Time	Username	Problem	Language	Result	Execution time	Memory
589375		MohamedFaresNebili	Split the sequence (APIO14_sequence)	C++14	50 / 100	615 ms	10272 KiB

sequence

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                using namespace std;

                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;

                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound
                #define int ll
                #define double ld

                const int MOD = 1000 * 1000 * 1000 + 7;
                const double EPS = 1e-9;

                int N, K;
                int A[100001], P[100001];
                int DP[1001][201], R[1001][201];
                int solve(int i, int t) {
                    if(i == N + 1 || t == 0) return 0;
                    if(DP[i][t] != -1) return DP[i][t];
                    int best = -1;
                    for(int l = i; l <= N - t; l++) {
                        int V = (P[l] - P[i - 1]) * (P[N] - P[l])
                            + solve(l + 1, t - 1);
                        if(V > best) best = V, R[i][t] = l;
                    }
                    return DP[i][t] = best;
                }

                int32_t main() {
                    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                    cin >> N >> K;
                    memset(DP, -1, sizeof DP);
                    for(int l = 1; l <= N; l++) {
                        cin >> A[l];
                        P[l] = A[l] + P[l - 1];
                    }
                    cout << solve(1, K) << "\n";
                    int curr = 1;
                    while(K > 0) {
                        cout << R[curr][K] << " ";
                        curr = R[curr][K] + 1; K--;
                    }
                    return 0;
                }

/**
7 3
4 1 3 4 0 2 3
**/

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