Submission #182110

#	Time	Username	Problem	Language	Result	Execution time	Memory
182110		lobo_prix	Split the sequence (APIO14_sequence)	C++17	89 / 100	1787 ms	91308 KiB

sequence

#include <bits/stdc++.h>

using namespace std;using f64 = double;using i64=long long;using u64=unsigned long long;
template<typename T> using Arr=vector<T>;
#define hfor(v, s, e) for(int v=(s);(s)<=v&&v<(e);++v)//half-opened range
#define hfori(v, s, e) for(int v=(e)-1;(s)<=v&&v<(e);--v)//inversion
#define hforo(v, s, e) int v=(s);for(;(s)<=v&&v<(e);++v)//out declaration
#define hforoi(v, s, e) int v=(e)-1; for(;(s)<=v&&v<(e);--v)
#define cfor(v, s, e) hfor(v,(s),(e)+1)//closed range
#define cfori(v, s, e) hfori(v,(s),(e)+1)
#define cforo(v, s, e) hforo(v,(s),(e)+1)
#define cforoi(v, s, e) hforoi(v,(s),(e)+1)
#define rep(v,x) hfor(v,0,(x))
#define repi(v,x) hfori(v,0,(x))
#define repo(v,x) hforo(v,0,(x))
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define cxp constexpr
#define PQ std::priority_queue

#ifndef DEBUG
	#pragma GCC optimize ("Ofast")
	auto __PRE_RUN__=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),(cout<<fixed<<setprecision(11)), 0);
#endif

template<typename T> cxp T inf() { return numeric_limits<T>::max() / 2; }
auto mapf(auto a, auto f){for(auto& x:a)x=f(x); return a;}
int rd(int lb, int ub){static mt19937 rng(time(0)^i64(new int)); return uniform_int_distribution<int>(lb, ub-1)(rng);}
int rd(int ub=inf<int>()){return rd(0,ub);}
const f64 pi=acosl(-1);

template<typename T>
struct Xarr: public Arr<T>{
	Xarr(int n=0, const T& init=T(), int offset=1):Arr<T>(n+offset, init), o(offset){}
	T& operator[](int i){return at(i);}
	T& at(int i){return Arr<T>::at(i+o);}
	const T& operator[](int i)const{return at(i);}
	const T& at(int i)const{return Arr<T>::at(i+o);}
	int o;
};
#define endl '\n'//not interactive?
#define int i64//MLE?
using pint = pair<int,int>;
using tint = tuple<int,int,int>;

struct Line{
	int tan, yic;
	f64 lx=-1/0.0, rx=1/0.0;

	int idx=0;
	bool operator<(const Line& r)const{return tan<r.tan;}
	bool operator<(const i64 x)const{return rx<x;}

	f64 intersectX(const Line& r)const{return (r.yic-yic)/f64(tan-r.tan);} 
	int f(int x)const{return tan*x+yic;}
};
struct StackCHT{
	Arr<Line> st;
	
	int idx=1;
	void push(i64 tan, i64 yic){
		Line f{tan, yic, 0, 1/0.0,idx++};
		while(sz(st)){
			f.lx=st.back().intersectX(f);
			if(tan==st.back().tan || f.lx<st.back().lx)
				st.popb();
			else
				break;
		}
		st.pushb(f);
	}

	int i=0;
	i64 get(i64 x){	
		while(i<sz(st) and st[i].lx<=x)
			i++;
		return st[i-1].tan*x+st[i-1].yic;
		//int s=0, e=sz(st);
		//while(e-s>1){
		//	int m=(s+e)/2;
		//	(x<st[m].lx?e:s)=m;
		//}
		//return st[s].tan*x + st[s].yic;
	}
};

Xarr<int> p(100000);
int dp[2][100000];
signed sav[201][100000];

void bt(int k, int i){
	if(!k)
		return;
	bt(k-1,sav[k][i]-1);
	cout<<sav[k][i]<<' ';
}

signed main(){
	int n,k; cin>>n>>k;
	int a[n];
	rep(i,n)
		cin>>a[i];
	rep(i,n)
		p[i]=p[i-1]+a[i];
	cfor(i,1,k){
		StackCHT s;
		s.push(p[0], -p[0]*p[0]+0);
		hfor(j,1,n){
			dp[i%2][j]=s.get(p[j]);
			s.push(p[j], -p[j]*p[j]+dp[(i+1)%2][j]);
			sav[i][j]=s.st[s.i-1].idx;
		}
	}
	cout<<dp[k%2][n-1]<<endl;
	bt(k,n-1);

	return 0;
}

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