Submission #975639

#	Time	Username	Problem	Language	Result	Execution time	Memory
975639		dosts	Split the sequence (APIO14_sequence)	C++17	71 / 100	323 ms	131072 KiB

sequence

//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 1e5+1, K = 2e2+1,inf = 1e18;


int dp[N][K];

bool Q;

struct Line {
	mutable int a,b,p;
	bool operator < (const Line& o) const{
		return Q ? p < o.p : a < o.a;
	};
};

struct CHT : multiset<Line> {
	int div(int a,int b) {
		return a/b - ((a^b) < 0 && a%b);
	}
	bool intersect(iterator x,iterator y) {
		if (y == end()) return x->p = inf,0;
		if (x->a == y->a) x->p = x->b <= y->b ? -inf : inf;
		else x->p = div(y->b-x->b,x->a-y->a);
		return x->p >= y->p;
	}

	void add(int a,int b) {
		auto z = insert({a,b,0}),y = z++,x = y;
		while (intersect(y,z)) z = erase(z);
		if (x != begin() && intersect(--x,y)) intersect(x,y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p) intersect(x,erase(y));
	}

	int query(int x) {
		Q = 1;
		auto it = *lower_bound({0,0,x});
		Q = 0;
		return it.a*x+it.b;
	}
};

void solve() {
	int n,k;
	cin >> n >> k;
	vi a(n+1),p(n+1,0);
	for (int i=1;i<=n;i++) cin >> a[i];	
	for (int i=1;i<=n;i++) p[i] = p[i-1]+a[i];
	for (int j=1;j<=k;j++) {
		CHT cht;
		cht.add(0,0);
		for (int i=1;i<=n;i++) {
			dp[i][j] = cht.query(p[i]);
			cht.add(p[i],dp[i][j-1]-(p[i]*p[i]));
		}
		cht.clear();
	}
	cout << dp[n][k] << endl;
	vi cuts;
	int ptr = n,ptr2 = k;
	while (ptr2) {
		for (int j=ptr-1;j>=1;j--) {
			if (dp[j][ptr2-1]+(p[ptr]-p[j])*p[j] == dp[ptr][ptr2]) {
				cuts.push_back(j);
				ptr = j;
				ptr2--;
				break;
			}
		}
	}
	reverse(cuts.begin(),cuts.end());
	for (auto it : cuts) cout << it << " ";
	cout << endl;
}
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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