Submission #538850

#	Time	Username	Problem	Language	Result	Execution time	Memory
538850		LucaDantas	Split the sequence (APIO14_sequence)	C++17	11 / 100	2078 ms	29940 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 __int128 inf = ((__int128)0x3f3f3f3f3f3f3f3f) * ((__int128)0x3f3f3f3f3f3f3f3f);

struct Line
{
	__int128 a, b, x; int id; // vou codar com inteiros msm
	Line(__int128 _a = 0, __int128 _b = 0, __int128 _x = inf, int _id = 0) : a(_a), b(_b), x(_x), id(_id) {}
	bool operator<(const Line& o) const { return a < o.a; } // change < for >, for min queries
	bool operator<(const __int128& o) const { return x < o; }
	__int128 eval(__int128 qr) { return a*qr + b; }
};

struct LineContainer : multiset<Line, less<>>
{
	bool hasNext(iterator it) { return next(it) != end(); }
	bool hasPrev(iterator it) { return it != begin(); }
	__int128 div(__int128 a, __int128 b) { return a / b - ((a^b)<0 && a%b); }
	__int128 intersect(Line l1, Line l2) { return div(l1.b-l2.b, l2.a-l1.a); }
	// double intersect(Line l1, Line l2) { return (double)(l1.b-l2.b)/(l2.a-l1.a); }
	bool bad(Line l1, Line l2, Line l3) { return intersect(l1, l3) <= intersect(l1, l2); }
	iterator get_x(iterator it) {
		if(!hasNext(it)) return it;
		Line l = *it;
		l.x = intersect(l, *next(it));
		erase(it);
		return insert(l);
	}
	void add(Line l) {
		auto it = lower_bound(l);
		__int128 a = l.a, b = l.b;
		if(it != end() && it->a == a) {
			if(it->b >= b) return;
			erase(it);
		}
		it = insert(l);
		if(hasPrev(it) && hasNext(it) && bad(*prev(it), *it, *next(it)))
			return (void)(erase(it));
		while(hasPrev(it) && hasPrev(prev(it)) && bad(*prev(prev(it)), *prev(it), *it))
			erase(prev(it));
		while(hasNext(it) && hasNext(next(it)) && bad(*it, *next(it), *next(next(it))))
			erase(next(it));
		it = get_x(it);
		if(hasPrev(it)) get_x(prev(it));
	}
	Line query(long long x) {
		assert(!empty());
		auto it = lower_bound(x);
		return *it;
	}
} 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.clear();
		cht.add(Line(suf[1], 0, inf, -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], inf, 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:97:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  int n, k; scanf("%d %d", &n, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%d", a+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