제출 #409324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409324		vuhoanggiap	수열 (APIO14_sequence)	C++17	100 / 100	674 ms	83140 KiB

sequence

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std; 
typedef long long ll; 
typedef long double ld; 

const ll INF = numeric_limits<ll>::max(); 

struct Line {
	ll k, m;
	int id;  
	ll f(const ll &x) { return k * x + m; }
	bool operator< (const Line &oth) {
		return mp(k, m) < mp(oth.k, oth.m); 
	}
}; 

struct cvh {
	int ptr = 0; 
	vector<Line> hull; 
	void reset() { ptr = 0; hull.clear(); }
	inline int sz() { return hull.size(); }
	bool bad(const Line &a, const Line &b, const Line &c) {
		if(b.k == c.k && b.m <= c.m) return true; 
		return (ld) (a.m - b.m) / (ld) (b.k - a.k) >= (ld) (b.m - c.m) / (ld) (c.k - b.k); 
	}
	void add(ll k, ll m, int id) {
		Line newline = {k, m, id}; 
		while(sz() >= 2 && bad(hull[sz() - 2], hull[sz() - 1], newline)) hull.pop_back(); 
		hull.pb(newline); 
	}
	Line query(ll x) {
		if(!sz()) {
			Line amogus = {-INF, -INF, -1}; 
			return amogus; 
		}
		if(ptr >= sz())
			ptr = sz() - 1;  
		while(ptr + 1 < sz() && hull[ptr].f(x) <= hull[ptr + 1].f(x)) ptr++; 
		return hull[ptr]; 
	}
} Cvh;

const int maxN = 1e5 + 5, maxK = 205; 
int n, k; 
int trace[maxK][maxN]; 
ll a[maxN], dp[maxN]; 

signed main() {
	cin >> n >> k; 
	for(int i = 1; i <= n; i++) {
		cin >> a[i]; 
		a[i] += a[i - 1];
	}
	dp[0] = -INF; 
	for(int i = 2; i <= k + 1; i++) {
		Cvh.reset(); 
		for(int j = 1; j <= n; j++) {
			Line best = Cvh.query(a[j]);
			if(dp[j] != -INF) 
				Cvh.add(a[j], dp[j] - a[j] * a[j], j); 
			trace[i][j] = best.id; 
			if(best.id != -1) 
				dp[j] = best.f(a[j]); 
			else
				dp[j] = -INF; 
		}
//		cout << i << '\n'; 
//		for(int j = 1; j <= n; j++) 
//			cout << dp[j] << ' '; 
//		cout << '\n'; 
	}	
	cout << dp[n] << '\n';
	vector<int> ans; 
	for(int i = k + 1, cur = n; i; i--) {
		ans.pb(trace[i][cur]); 
		cur = trace[i][cur]; 
	}
	for(int i = (int)ans.size() - 1; i >= 0; i--) 
		if(ans[i]) cout << ans[i] << ' '; 
}

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