Submission #197797

#	Time	Username	Problem	Language	Result	Execution time	Memory
197797		dennisstar	Split the sequence (APIO14_sequence)	C++17	49 / 100	1578 ms	131076 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ryan bear
#define sq(X) ((X)*(X))
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = (1ll<<60);

struct line {
	ll a, b; int ind;
	ll get(ll x) { return a*x+b; }
	line() {}
	line(ll A, ll B, int i) { a=A, b=B, ind=i; }
};

struct LiChao {
	vlm l, r;
	vector<line> L;
	void init() { l.resize(2); r.resize(2); L.resize(2); L[1]=line(0, -INF, 0); }
	inline void upd(int now, line &v, ll s, ll e) {
		ll md=(s+e)/2;
		line lo=L[now], hi=v;
		if (lo.get(s)>hi.get(s)) swap(lo, hi);
		if (lo.get(e)<=hi.get(e)) { L[now]=hi; return ; }

		if (lo.get(md)>=hi.get(md)) {
			L[now]=lo;
			if (!l[now]) { l[now]=l.size(); l.eb(0); r.eb(0); L.eb(0, -INF, 0); }
			upd(l[now], hi, s, md);
		}
		else {
			L[now]=hi;
			if (!r[now]) { r[now]=r.size(); l.eb(0); r.eb(0); L.eb(0, -INF, 0); }
			upd(r[now], lo, md+1, e);
		}
	}
	inline pll get(int now, ll x, ll s, ll e) {
		if (!now) return pll(-INF, 0);
		ll md=(s+e)/2;
		if (x<=md) return max(pll(L[now].get(x), L[now].ind), get(l[now], x, s, md));
		else return max(pll(L[now].get(x), L[now].ind), get(r[now], x, md+1, e));
	}
}lct[205];

int N, K; vlm ar; ll mx; int mi; vim lst[205];

void dfs(int k, int i) {
	if (!k) return ;
	dfs(k-1, lst[k][i]);
	printf("%d ", i);
}

int main() {
	scanf("%d %d", &N, &K); ar.resize(N+1);
	for (int i=1; i<=N; i++) { scanf("%lld", &ar[i]); ar[i]+=ar[i-1]; }
	for (int i=0; i<=K; i++) { lct[i].init(); lst[i].resize(N+1); }
	line im;
	im=line(ar[N], 0, 0); lct[0].upd(1, im, 0, INF);
	for (int i=1; i<N; i++) {
		if (i>=K) {
			auto k=lct[K-1].get(1, ar[i], 0, ar[N]);
			if (mx<=k.fi-ar[i]*ar[i]) mx=k.fi-ar[i]*ar[i], mi=i;
		}
		for (int j=min(i, K); j; j--) {
			auto k=lct[j-1].get(1, ar[i], 0, ar[N]); k.fi-=ar[i]*ar[i];
			lst[j][i]=k.se;
			im=line(ar[N]+ar[i], k.fi-ar[N]*ar[i], i); lct[j].upd(1, im, 0, ar[N]);
		}
	}
	printf("%lld\n", mx);
	dfs(K, mi); puts("");
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &K); ar.resize(N+1);
  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:65:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) { scanf("%lld", &ar[i]); ar[i]+=ar[i-1]; }
                             ~~~~~^~~~~~~~~~~~~~~~

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