Submission #106048

#	Time	Username	Problem	Language	Result	Execution time	Memory
106048		Saboon	수열 (APIO14_sequence)	C++14	22 / 100	4 ms	512 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 100 + 10;

ll a[maxn], par[maxn], dp[maxn], m[210][maxn];

struct line{
	ll a; // shib
	ll b; // arz az mabda
	int idx;
	line(ll a_ = 0, ll b_ = 0, int idx_ = 0){
		a = a_, b = b_, idx = idx_;
	}
	ll gety(ll x){
		return a * x + b;
	}
};

stack<line> Q;

bool isgood(line fi, line se, line th){
	return 1ll * (se.b - fi.b) * (fi.a - th.a) < 1ll * (th.b - fi.b) * (fi.a - se.a);
}

bool parallel(line fi, line se){
	return fi.a == se.a;
}

void add(ll a, ll b, int idx){ // y = ax + b
	line nw = line(a, b, idx);
	if (!Q.empty() and parallel(nw, Q.top())){
		if (parallel(nw, Q.top())){
			if (b >= Q.top().b){
				line nex = Q.top();
//				cout << "parallel Deleted " << nex.a << " " << nex.b << " " << nex.idx << endl;
				Q.pop();
			}
			else
				return;
		}
	}
	while (Q.size() > 1){
		line nex = Q.top();
		Q.pop();
		line other = Q.top();
		if (isgood(other, nex, nw)){
			Q.push(nex);
			break;
		}
//		cout << "Deleted " << nex.a << " " << nex.b << " " << nex.idx << endl;
	}
//	cout << "Added " << nw.a << " " << nw.b << " " << nw.idx << endl;
	Q.push(nw);
}

pair<ll, int> get(ll x, int idx){
	while (!Q.empty() and Q.top().idx >= idx)
		Q.pop();
	if (Q.empty())
		return {0, 0};
	while (Q.size() > 1){
		line nw = Q.top();
		Q.pop();
		if (nw.gety(x) > Q.top().gety(x)){
			Q.push(nw);
			break;
		}
	}
//	cout << x << " -> " << Q.top().a << " " << Q.front().b << " " << Q.front().idx << endl;
	return {Q.top().gety(x), Q.top().idx};
}

void vitex(){
	while (!Q.empty())
		Q.pop();
}

int main(){
	ios_base::sync_with_stdio (false);
	int n, k;
	cin >> n >> k;
	k ++;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		par[i] = par[i - 1] + a[i];
	}
	for (int i = 1; i <= k; i++){
		for (int j = n; j >= 1; j--){
			if (i == 1){
				dp[j] = 0;
				continue;
			}
			auto it = get(par[j], j);
			dp[j] = it.first;
			m[i][j] = it.second;
		}
		vitex();
		for (int j = 1; j <= n; j++)
			add(par[j], dp[j] - par[j] * par[j], j);
	}
	cout << dp[n] << endl;
	int p = k, q = n;
	while (p > 1){
		cout << m[p][q] << " ";
		q = m[p][q];
		p --;
	}
	cout << endl;
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void add(ll, ll, int)':
sequence.cpp:39:10: warning: variable 'nex' set but not used [-Wunused-but-set-variable]
     line nex = Q.top();
          ^~~

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