Submission #589755

#	Time	Username	Problem	Language	Result	Execution time	Memory
589755		MohamedFaresNebili	Split the sequence (APIO14_sequence)	C++14	100 / 100	458 ms	81804 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;
                ll A[100001], DP[2][100001];
                int P[201][100001], Q[100001];

                ll area(int a, int b, int c) {
                    return (DP[0][b] - DP[0][a]) - (A[b] - A[a]) * (A[N] - A[c]);
                }
                ll cross(int a, int b, int c) {
                    return (DP[0][b] - DP[0][a]) * (A[c] - A[b])
                        -  (DP[0][c] - DP[0][b]) * (A[b] - A[a]);
                }

                int32_t main() {
                    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                    cin >> N >> K;
                    for(int l = 1; l <= N; l++) {
                        cin >> A[l];
                        A[l] += A[l - 1];
                    }
                    for(int l = 1; l <= K; l++) {
                        int L = 1, R = 1; Q[R++] = 0;
                        for(int i = 1; i <= N; i++) {
                            while(R - L > 1 && area(Q[L], Q[L + 1], i) >= 0) L++;
                            int V = Q[L];
                            DP[1][i] = DP[0][V] + (A[i] - A[V]) * (A[N] - A[i]);
                            P[l][i] = V;
                            while(R - L > 1 && cross(Q[R - 2], Q[R - 1], i) <= 0) R--;
                            Q[R++] = i;
                        }
                        swap(DP[0], DP[1]);
                    }
                    ll res = -1; int curr = 0;
                    for(int l = 1; l <= N; l++) {
                        if(DP[0][l] > res)
                            res = DP[0][l], curr = l;
                    }
                    cout << res << "\n";
                    while(K > 0) {
                        cout << curr << " ";
                        curr = P[K][curr]; K--;
                    }
                    return 0;
                }

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