Submission #979719

#	Time	Username	Problem	Language	Result	Execution time	Memory
979719		vjudge1	Split the sequence (APIO14_sequence)	C++14	0 / 100	4041 ms	131076 KiB

sequence

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

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define for_(i, s, e) for (ll i = s; i < (ll)e; i++)
#define for__(i, s, e) for (ll i = s; i > (ll)e; i--)
#define mod(x) ((x) % MOD)
#define mid(x) midpoint(x)
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define bg begin()
#define ed end()
#define sz(a) int(a.size())
#define all(x) (x).bg, (x).ed
#define allr(x) x.rbegin(), x.rend()
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define nl "\n"
#define _ << ' ' <<
#define pb emplace_back
#define MP make_pair
#define UB upper_bound
#define LB lower_bound
#define ff first
#define ss second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
const ll MOD = 1e9 + 7; // 998244353;

template <typename T1, typename T2>
inline istream &operator>>(istream &in, pair<T1, T2> &a)
{
  in >> a.ff >> a.ss;
  return in;
}
template <typename T1, typename T2>
inline ostream &operator<<(ostream &out, pair<T1, T2> a)
{
  out << a.ff << " " << a.ss;
  return out;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &v)
{
  for_(i, 0, sz(v)) cin >> v[i];
  return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &v)
{
  for_(i, 0, sz(v)) cout << v[i] << " ";
  return out;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(pair<T1, T2> &l, pair<T1, T2> &r) { return {l.ff + r.ff, l.ss + r.ss}; }
#define int long long

struct line
{
	int m;
	int c;
	int num;
	line(int _m, int _c, int _nm) : m(_m), c(_c), num(_nm) {}
	friend double presek(const line l1, const line l2) { return (double)(l2.c - l1.c) / (double)(l1.m - l2.m); }
	int operator()(int x) { return m*x + c; };
};

int32_t par[205][100005];
vector<int> dp1(100005);
vector<int> dp2(100005);
deque<line> dq;

void solve()
{
  int n,k;cin>>n>>k;
  vector<int>a(n+1,0);
  for(int i=1;i<=n;i++) cin>>a[i];
  vector<int>pref(n+1,0);
  for(int i=1;i<=n;i++) pref[i]=pref[i-1]+a[i];
  for (int i = 1; i <= k+1; i++)
	{
		dq.clear();
		for (int j = 1; j <= n; j++)
		{
			line tr(pref[j-1], dp1[j-1]-pref[n]*pref[j-1], j-1);
			while (dq.size() >= 2 && presek(tr, dq[dq.size()-1]) <= presek(dq[dq.size()-2], tr))
				dq.pop_back();
			dq.push_back(tr);
			while (dq.size() >= 2 && dq[0](pref[j]) <= dq[1](pref[j]))
				dq.pop_front();
			dp2[j] = dq[0](pref[j]) + pref[j]*pref[n]-pref[j]*pref[j];
			par[i][j] = dq[0].num;
		}
		dp1 = dp2;
	}
	cout << dp1[n] << '\n';
	int32_t tr = n;
	for (int i = k+1; i > 1; i--)
	{
		tr = par[i][tr];
		cout << tr << " ";
	}
	cout << "\n";
}

signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int tt = 1;
  cin >> tt;
  while (tt--)
    solve();

  return 0;
}

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