Submission #312191

#	Time	Username	Problem	Language	Result	Execution time	Memory
312191		minhcool	Split the sequence (APIO14_sequence)	C++17	100 / 100	1726 ms	84344 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define ins insert
#define er erase
 
typedef pair<long long, long long> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
/*
For educational purposes, I will implement the solution both in divide_and_conquer_DP style - O(N * K * log2(N)) (probably get 71 points) and convex hull trick style - O(N * K)
This code is divide_and_conquer DP
*/
 
const int N = 2e5 + 5, K = 205;
 
long long n, k, a[N], suff[N];
long long dp[N], lst_dp[N];
int opt[N];
int lst[N][K];
 
long long f(int i, int j){
    return lst_dp[j] + (suff[j + 1] - suff[i + 1]) * suff[i + 1];
}
 
/*
Condition of D&Q DP: optimal position of x <= optimal position of (x + 1)
Suppose we are trying to calculate the value of opt[x] with l <= x <= r
We take the middle element mid = (l + r) >> 1 and calulate its opt value = y
=> opt[x] < y with l <= x < mid, and opt[x] > y with mid < x <= r
We can easily see that the complexity is O(n * log2(n))
I will say that this D&Q is nice
*/
 
void divide(int l, int r, int optl, int optr){
    if(l > r) return;
    //cout << l << " " << r << " " << optl << " " << optr << "\n";
    if(optl == optr){
        for(int i = l; i <= r; i++){
            opt[i] = optl;
        }
        return;
    }
    int mid = (l + r) >> 1;
    ii best = {-1, oo};
    for(int i = optl; i <= min(optr, mid - 1); i++){
        best = max(best, {f(mid, i), i});
        //if(mid == 4) cout << mid << " " << f(mid, i) << "\n";
    }
    opt[mid] = best.se;
    divide(l, mid - 1, optl, best.se);
    divide(mid + 1, r, best.se, optr);
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = n; i >= 1; i--) suff[i] = (suff[i + 1] + a[i]);
	for(int i = 1; i <= k; i++){
	    for(int j = 1; j <= n; j++){
	        opt[j] = 0;
	        lst_dp[j] = dp[j];
	    }
	    divide(1, n, 0, n - 1);
	    for(int j = 1; j <= n; j++) lst[j][i] = opt[j];
	    for(int j = 1; j <= n; j++) dp[j] = f(j, opt[j]);
	    //for(int j = 1; j <= n; j++) cout << i << " " << j << " " << dp[j] << " " << opt[j] << "\n";
	}
    int ind = k;
    for(int i = k + 1; i <= n; i++){
        if(dp[i] > dp[ind]) ind = i;
    }
    cout << dp[ind] << "\n";
    vector<int> pos;
    pos.clear();
    int tmp = k;
    while(tmp){
        pos.pb(ind);
        ind = lst[ind][tmp];
        tmp--;
    }
    for(int i = pos.size() - 1; i >= 0; i--) cout << pos[i] << " ";
}
 

Compilation message (stderr)

sequence.cpp:14:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

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