Submission #838929

#	Time	Username	Problem	Language	Result	Execution time	Memory
838929		TrinhKhanhDung	Split the sequence (APIO14_sequence)	C++14	50 / 100	183 ms	6212 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)x.size()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(k) (1LL << (k))
#define fi first
#define se second
#define v1 vector<unsigned int>
#define v2 vector<v1>
#define INF (int)(1e9)
#define lim (int)(1000000)
#define MAX (int)(100003)
#define MAX_K (int)(203)
#define MOD (ll)(1000000007)

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template <class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template <class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

using namespace std;

int N, K;
int a[MAX], trace[1003][MAX_K];
ll pre[MAX], dp[1003][MAX_K];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

//    freopen("sequence.in", "r", stdin);
//    freopen("sequence.out", "w", stdout);

    cin >> N >> K;
    for(int i=1; i<=N; i++){
        cin >> a[i];
        pre[i] = pre[i-1] + 1ll * a[i];
    }

    K++;
    memset(dp, -0x3f, sizeof dp);
    dp[0][0] = 0;

    for(int k=1; k<=K; k++){
        for(int i=k; i<=N; i++){
            for(int j=k; j<=N; j++){
                if(maximize(dp[i][k], dp[j-1][k-1] + pre[j-1] * (pre[i] - pre[j-1]))){
                    trace[i][k] = j-1;
                }
            }
        }
    }

    cout << dp[N][K] << '\n';

    stack<int> ans;
    int u = trace[N][K];
    for(int i=K-1; i>=1; i--){
        ans.emplace(u);
        u = trace[u][i];
    }

    while(!ans.empty()){
        cout << ans.top() << ' ';
        ans.pop();
    }

    return 0;
}

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