Submission #498424

#	Time	Username	Problem	Language	Result	Execution time	Memory
498424		Nalrimet	Split the sequence (APIO14_sequence)	C++17	22 / 100	477 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;
ll a[N], b[N], pref[N], suma, dp[N][205];
bool cut[N][205], used[N];
vector<int> ans;

ll f(int i, int j, int m){
//    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]);
}

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

    cin >> n >> k;
    k1 = k;
    k++;

    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    for(int i = 0; i <= n; ++i){
        for(int j = 2; j <= k; ++j){
            dp[i][j] = -inf;
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 2; j <= k; ++j){
            int l = 0, r = i - 1;
            while(r - l > 2){
                int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
                if(f(i, j, m1) < f(i, j, m2))
                    l = m1;
                else
                    r = m2;
            }
//            cout << l << ' ' << r << '\n';
            if(f(i, j, l) >= f(i, j, l + 1)) r = l;
            else if(l + 1 < i) l++;
            if(l + 1 < i && f(i, j, l) >= f(i, j, l + 1)) r = l;
            else if(l + 1 < i) l++;

            dp[i][j] = f(i, j, l);
            if(dp[i][j - 1] > dp[i][j] && dp[i][j - 1] > dp[i - 1][j]){
                par[i][j] = par[i][j - 1];
                cut[i][j] = cut[i][j - 1];
                dp[i][j] = dp[i][j - 1];
            }
            else if(dp[i][j] > dp[i - 1][j]) {
                cut[i][j] = 1;
                par[i][j] = l;
            }
            else{
                dp[i][j] = dp[i - 1][j];
                par[i][j] = i - 1;
            }
//            cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
        }
    }
    cout << dp[n][k] << '\n';

    int ind = n;
    while(ind != 0){
        if(cut[ind][k]) {
            ans.pb(ind);
            used[ind] = 1;
            ind = par[ind][k];
            k--;
        }
        else ind = par[ind][k];
    }

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

    ind = 1;
//    cout << ans.size() << '\n';
    while(ans.size() < k1){
//        cout << ans.size() << ' ' << ind << '\n';
        while(used[ind]) ind++;
        ans.pb(ind);
        used[ind] = 1;
    }

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

Compilation message (stderr)

sequence.cpp:26:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 |  main(){
      |  ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:95:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |     while(ans.size() < k1){
      |           ~~~~~~~~~~~^~~~

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