Submission #33579

#	Time	Username	Problem	Language	Result	Execution time	Memory
33579		sinhriv	Split the sequence (APIO14_sequence)	C++14	11 / 100	29 ms	131072 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;
const int K = 220;

int n, k;
int arr[N];
int pre[N][K];
long long f[N][K];

template < class T > 
struct LineIT{
	/// Lim 
	static const T inf = -2e9;
	static const T Worst = -1e18;
 
	struct Line{
		T a;
		T b;
		int idx;
 
		T get(T x){
			if(a < inf) return Worst; 
			return a * x + b;
		}
	};
 
 
	T low, high;
 
	int root, cnt;
	vector < int > L;
	vector < int > R;	
	vector < Line > it;
 
	Line Create(T u, T v, int i){
		Line ret;
		ret.a = u;
		ret.b = v;
		ret.idx = i;
		return ret;
	}
 
	LineIT(T from, T to){
		low = from;
		high = to;
		L.resize(N * 10 + 10, 0);
		R.resize(N * 10 + 10, 0);
		it.resize(N * 10 + 10, Create(inf - 1, inf - 1, 0));
		root = cnt = 1;
	}
 
	T lef, rig;
 
 
	void upd(int &x, T l, T r, Line val){
		if(l > rig || r < lef) return;
 
 
		if(x == 0) x = ++cnt;
 
		T mid  = ((l + r) >> 1);
 
 
 		if(l >= lef && r <= rig){
			if(it[x].get(l) >= val.get(l) && it[x].get(r) >= val.get(r)){
				return;
			}
			
			if(it[x].get(l) <= val.get(l) && it[x].get(r) <= val.get(r)){
				it[x] = val;
				return;
			}
	 
			if(it[x].get(l) <= val.get(l) && it[x].get(mid) <= val.get(mid)){
				upd(R[x], mid + 1, r, it[x]);
				it[x] = val;
				return;
			}
	 
			if(it[x].get(l) >= val.get(l) && it[x].get(mid) >= val.get(mid)){
				upd(R[x], mid + 1, r, val);
				return;
			}
	 
			if(it[x].get(mid + 1) <= val.get(mid + 1) && it[x].get(r) <= val.get(r)){
				upd(L[x], l, mid, it[x]);
				it[x] = val;
				return;
			}
	 
			if(it[x].get(mid + 1) >= val.get(mid + 1) && it[x].get(r) >= val.get(r)){
				upd(L[x], l, mid, val);
				return;
			}
		}
		upd(L[x], l, mid, val);
		upd(R[x], mid + 1, r, val);
	}

	Line M(Line x, Line y, T val){
		if(x.get(val) > y.get(val)) return x;
		return y;
	}
 
	Line query(int x, int l, int r, T val){
		if(l > val || r < val || x == 0) return Create(inf - 1, inf - 1, 0);
 
		if(l == r) return it[x];
		T mid  = ((l + r) >> 1);
 
		Line ans = it[x];
 
 
		ans = M(ans, query(L[x], l, mid, val), val);
		ans = M(ans, query(R[x], mid + 1, r, val), val);
 
		return ans;
	}
 
	void update(T a, T b, int idx, pair < T, T > seg = make_pair(-inf - 1, -inf - 1)){
		if(seg.first != -inf - 1){
			lef = seg.first;
			rig = seg.second;
		}
		else{
			lef = low;
			rig = high;
		}
		upd(root, low, high, Create(a, b, idx));
	}
 
	pair < T, int > ask(T x){
		Line p = query(root, low, high, x);
		return make_pair(p.get(x), p.idx);
	}
};

long long solve(vector < int > a){
	vector < LineIT < long long > > tree;
	for(int i = 0; i <= k; ++i){
		tree.emplace_back(0, 1e9);
	}

	vector < long long > sum(a.size());
	partial_sum(a.begin(), a.end(), sum.begin());

	long long ans = 0;

	tree[0].update(0, 0, 0);
	for(int j = 1; j <= k; ++j){
		for(int i = 1; i <= n; ++i){
			auto p = tree[j - 1].ask(sum[i]);
			pre[i][j] = p.second;
			f[i][j] = p.first + sum[i] * sum[n] - sum[i] * sum[i];
			tree[j].update(sum[i], -sum[i] * sum[n] + f[i][j], i);
			if(j == k) ans = max(ans, f[i][j]);
		}
	}

	return ans;
}


int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	scanf("%d%d", &n, &k);
	vector < int > x(1, 0);

	for(int i = 1; i <= n; ++i){
		scanf("%d", arr + i);
		x.push_back(arr[i]);
	}
	vector < int > lst;

	long long ans = solve(x);
	int pos = 0;
	for(int i = 1; i < n; ++i){
		if(f[i][k] == ans){
			pos = i;
		}
	}
	for(int j = k; j >= 1; --j){
		lst.push_back(pos);
		pos = pre[pos][j];
	}
	reverse(lst.begin(), lst.end());

	printf("%lld\n", ans);

	for(int x : lst){
		printf("%d ", x);
	}



	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:169:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
sequence.cpp:172:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:176:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", arr + i);
                       ^

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