Submission #538862

#	Time	Username	Problem	Language	Result	Execution time	Memory
538862		LucaDantas	Split the sequence (APIO14_sequence)	C++17	100 / 100	836 ms	84268 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

long long dv(long long a, long long b) { return a / b /*- ((a^b)<0 && a%b)*/; }

struct Line {
	long long a, b; int id;
	Line(long long _a, long long _b, int _id) : a(_a), b(_b), id(_id) {}
	long long intersect(Line L) { return dv(L.b-b, a-L.a); }
	// double intersect(const Line& L) const { return (double)(L.b-b) / (a-L.a); }
	long long eval(long long x) { return a*x + b; }
};


struct CHT {
	deque<Line> cht;
	void add(Line L) {
		if(cht.size() && cht.front().a == L.a) {
			if(cht.front().b > L.b) return;
			cht.pop_front();
		}
		while(cht.size() >= 2 && L.intersect(cht[1]) < L.intersect(cht[0]))
			cht.pop_front();
		cht.push_front(L);
	}
	Line query(int x) {
		/* Line ans(-1, -1, -1);
		for(Line l : cht)
			if(l.eval(x) > ans.eval(x)) ans = l;
		return ans; */
		while(cht.size() >= 2 && cht[ cht.size() - 2 ].eval(x) >= cht.back().eval(x))
			cht.pop_back();
		return cht.back();
	}
} cht;



constexpr int maxn = 2e5+10, maxk = 210;

int a[maxn];
long long suf[maxn];
long long dp[2][maxn];
int opt[maxk][maxn];

int32_t main() {
	int n, k; scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; i++)
		scanf("%d", a+i);
	
	// dp[i] = dp[j] + suf[i+1] * (suf[j+1] - suf[i+1])
	// dp[i] = dp[j] + {suf[j+1] * suf[i+1]} - (suf[i+1]^2)

	for(int i = n; i >= 1; i--)
		suf[i] = a[i] + suf[i+1];

	for(int i = 1; i <= k; i++) {
		cht.cht.clear();
		cht.add(Line(suf[1], 0, -1));
		
		for(int j = 1; j <= n; j++) {
			Line bom = cht.query(suf[j+1]);

			opt[i][j] = bom.id;
			dp[1][j] = bom.eval(suf[j+1]) - 1ll*suf[j+1]*suf[j+1];

			cht.add(Line(suf[j+1], dp[0][j], j));
		}

		for(int j = 1; j <= n; j++)
			dp[0][j] = dp[1][j], dp[1][j] = 0;
	}

	long long ans = 0;
	for(int j = 1; j < n; j++)
		if(dp[0][j] >= dp[0][ans]) ans = j;

	printf("%lld\n", dp[0][ans]);

	for(int i = 0; i < k; i++)
		assert(ans >= 0), printf("%lld ", ans), ans = opt[k-i][ans];
	puts("");
}

Compilation message (stderr)

sequence.cpp: In function 'int32_t main()':
sequence.cpp:47:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  int n, k; scanf("%d %d", &n, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d", a+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