Submission #683215

#	Time	Username	Problem	Language	Result	Execution time	Memory
683215		theartofwar	Split the sequence (APIO14_sequence)	C++14	39 / 100	793 ms	131072 KiB

sequence

#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define rsrt(v) sort(v.begin(), v.end(), greater<int>())
#define srt(v) sort(v.begin(),v.end())
#define all(x) (x).begin(),(x).end()
#define ll long long
#define int long long
ll md = 1000000007;
int inf = 1e18;
using namespace std;
template <typename T>
T pw(T a, T b) {T c = 1, m = a;while(b) {if (b & 1) c=(c*m); m=(m*m); b/=2;} return c;}
template <typename T>
T ceel(T a, T b){if (a%b==0) return a/b; else return a/b + 1;}
template <typename T>
T gcd(T a, T b) {return b == 0 ? a : gcd(b, a % b);}
ll pwmd(ll a, ll b) {ll c = 1, m = a%md;while(b) {if (b & 1) c=(c*m)%md; m=(m*m)%md; b/=2;} return c;}
ll modinv(ll n){return pwmd(n, md - 2);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r){ // gives random number in [l,r]
  return uniform_int_distribution<ll>(l, r)(rng);
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << '{' << p.first << ", " << p.second << '}';
}
template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
  os << '[';
  for (auto it = c.begin(); it != c.end(); ++it)
    os << &", "[2 * (it == c.begin())] << *it;
  return os << ']';
}
//support up to 5 args
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
  _NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0)     \
  (MACRO, ##__VA_ARGS__)
// #ifdef LOCAL
#define out(x) #x " = " << x << "; "
#define dbg(...)                                                              \
  cerr << "Line " << __LINE__ << ": " FOR_EACH_MACRO(out, __VA_ARGS__) << "\n"
// #else
// #define debug(...) 42
// #endif
//--------------------------------theartofwar-------------------------------------------//
// This is for maximum query, for minimum query you can make slope and intercept -ve
struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) { // k = slope, m = intercept
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	pair<int, int> query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return {l.k,  l.m};
	}
};
signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	vector<LineContainer> vlc;
	for (int i = 0; i <= k + 1; i++) {
		LineContainer tmp;
		vlc.push_back(tmp);
	}
	vector<vector<int>> dp(n, vector<int>(k + 2)), rev(n, vector<int>(k + 2, -1));
	map<pair<int, int>, int> pos[k + 2];
	int pre = 0;
	for (int i = 0; i < n; i++) {
		pre += v[i];
		vlc[1].add(pre, 0 - pre * pre);
		pos[1][{pre, 0 - pre * pre}] = i;
		for (int j = k + 1; j >= 2; j--) {
			if (j > i + 1) continue;
			int a, b;
			auto p = vlc[j - 1].query(pre);
			a = p.first, b = p.second;
			rev[i][j] = pos[j - 1][p];
			int a0 = a * pre + b;
			dp[i][j] = a0;
			pos[j][{pre, a0 - pre * pre}] = i;
			vlc[j].add(pre, a0 - pre * pre);
		}
	}
	cout << dp[n - 1][k + 1] << "\n";
	vector<int> seq;
	int e = k + 1, f = n - 1;
	while (e > 1) {
		f = rev[f][e], e--;
		seq.push_back(f);
	}
	srt(seq);
	for (auto s : seq) cout << (s + 1) << " ";
}


/* 

1,1,1,1,1,1

a, b, c, d, e, f

(a, b) (c, d) (e, f)

(a + b)(c + d + e + f) + (c + d)(e + f) = (a + b)(c + d) + (a + b)(e + f) + (c + d)(e + f)

(e + f)(a + b + c + d)  + (a + b)(c + d)

(a + b)(c + d) + (a + b)(e + f) + (c + d)(e + f)

(x - s0) * s0 + a0

s0 * x + a0 - s0 * s0

a, b, c, d

ab + c(a + b) + d(a + b + c)
a(b + c) + b(c + d) + d(a + b)
4, 4, 4, 5
16 + 32 + 60 = 108


8 4 5
32 + 



 */

Compilation message (stderr)

sequence.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("unroll-loops")
      |

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