Submission #498478

#	Time	Username	Problem	Language	Result	Execution time	Memory
498478		Nalrimet	Split the sequence (APIO14_sequence)	C++17	0 / 100	65 ms	131076 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define S second
#define F first

//const int inf = 1e18;
const int N = 100005;
const ll inf = 1e18;

int n, y, k, par[N][205], k1, ind;
ll a[N], b[N], pref[N], suma, dp[N][205], sz[N][205];
bool cut[N][205], used[N];
vector<int> ans;

ll f(int i, int j, int m){
//    if(dp[m][j - 1] == -inf) return -inf;
//    cout << i << ' ' << j << ' ' << m << '\n';
//    cout << dp[m][j - 1] << ' ' << (pref[i] - pref[m]) << ' ' << (pref[n] - pref[i]) << '\n';
    return dp[m][j - 1] + (pref[i] - pref[m]) * (pref[n] - pref[i]);
//
//    (a - b) * (c - a)
//    ac-a^2-bc+ab
//    -(a * a) + (ab)
//    a(b-a)
//    pref[n] *
//    -pref[i] * //
//    pref[m] *
//    (pref[i]*pref[n])-(pref[i] * pref[i]) + pref[m] * pref[i] - pref[m]*pref[n]
//    dp[m][j - 1] +
}

 main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    cin >> n >> k;
    k1 = k;
    k++;
    dp[0][k] = -1;

    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }
    for(int j = 2; j <= k; ++j){
        for(int i = 1; i <= n; ++i){
            dp[i][j] = -1;
            if(f(i, j, i - 1) > dp[i][j]){
                dp[i][j] = max(dp[i][j], f(i, j, i - 1));
                par[i][j] = i - 1;
                sz[i][j] = sz[i - 1][j - 1] + 1;
            }
            if(f(i, j, par[i - 1][j]) > dp[i][j]){
                dp[i][j] = max(dp[i][j], f(i, j, par[i - 1][j]));
                par[i][j] = par[i - 1][j];
                sz[i][j] = sz[i - 1][j];
            }
//            cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
        }
    }
    for(int i = n - 1; i >= 1; --i){
        if(sz[i][k] == k - 1 && dp[i][k] > dp[ind][k]){
            ind = i;
        }
    }
    cout << dp[ind][k] << '\n';
    while(ind != 0){
        ans.pb(ind);
        ind = par[ind][k];
        k--;
    }

    reverse(ans.begin(), ans.end());

    for(auto to : ans){
        cout << to << ' ';
    }
}

Compilation message (stderr)

sequence.cpp:37:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 |  main(){
      |  ^~~~

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