Submission #260520

#	Time	Username	Problem	Language	Result	Execution time	Memory
260520		shayan_p	Split the sequence (APIO14_sequence)	C++14	100 / 100	1448 ms	82808 KiB

sequence

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, maxk = 210, mod = 1e9 + 7;
const ll inf = 1e18 + 10;

int a[maxn];
ll dp[maxn], divi[maxn], cst[maxn], sm[maxn], sm2[maxn];
int restore[maxk][maxn], bef[maxn];

ll f(int l, int r){
    return 1ll * (sm[r] - sm[l-1]) * (sm[r] - sm[l-1]) - (sm2[r] - sm2[l-1]) + dp[l-1];
}
void solve(int l, int r, int L, int R){
    if(l > r)
	return;
    int mid = (l+r) >> 1;
    divi[mid] = inf;
    int pos = -1;
    for(int i = min(mid, R); i >= L; i--){
	ll num = f(i, mid);
	if(num < divi[mid])
	    divi[mid] = num, pos = i;
    }
    bef[mid] = pos - 1;
    solve(l, mid-1, L, pos);
    solve(mid+1, r, pos, R);
}
    
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, k;
    cin >> n >> k;
    ++k;
    for(int i = 1; i <= n; i++){
	cin >> a[i];
	sm[i] = sm[i-1] + a[i];
	sm2[i] = sm2[i-1] + 1ll * a[i] * a[i];
    }
    for(int i = 1; i <= n; i++){
	dp[i] = sm[i] * sm[i] - sm2[i];	
    }
    for(int i = 2; i <= k; i++){
	solve(1, n, 1, n);
	memcpy(dp, divi, sizeof dp);
	memcpy(restore[i], bef, sizeof bef);
    }
    ll ANS = (1ll * sm[n] * sm[n] - sm2[n] - dp[n]) / 2;
    vector<int> v;
    int tmp = n;
    for(int i = k; i >= 2; i--){
	tmp = restore[i][tmp];
	v.PB(tmp);
    }
    reverse(v.begin(), v.end());
    cout << ANS << "\n";
    for(int x : v){
	cout << x << " ";
    }
    return cout << endl, 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