Submission #1264045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264045		_rain_	Split the sequence (APIO14_sequence)	C++17	71 / 100	271 ms	196608 KiB

sequence

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

#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1) << (x))
#define BIT(mask , x) (((mask)>>(x))&(1))
#define sz(x) (int)(x).size()

template<class T1 , class T2>	
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() ,data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}

const LL inf = (LL) 1e18;
const int N = (int) 1e5;
const int MAXK = (int) 200;
	int a[N + 2];
	int n , k;
	
namespace subtask2{
	bool check(){
		return n <= N;
	}
	
	LL dp[2][MAXK + 2] = {};
	int trace[N + 2][MAXK + 2];
	LL pre[N + 2] = {};
	
		struct Line{
			LL a , b ;
			int id;
			Line() {};
			Line(LL a , LL b , int id) : a(a) , b(b) , id(id) {};
		};
		
		class Convex_Hull{
			public:
				vector<Line>line;
				int p = 1;
					bool compare1(Line a , Line b , Line c){
						LL t1 = (b.b - a.b) , t2 = (c.b - a.b);
						LL x1 = (a.a - b.a) , x2 = (a.a - c.a);
						return t1 * x2 >= t2 * x1;
					}
					
					bool compare2(Line a , Line b , LL t){
						LL t1 = (b.b - a.b) , t2 = (a.a - b.a);
						return t1 >= t * t2;
					}
					
					LL F(Line a , LL x){
						return a.a * x + a.b;
					}
					
					void insert_line(Line x){
						int sz = sz(line) ;
						while (sz >= 2 && compare1(line[sz - 2] , line[sz - 1] , x)) {
							line.pop_back();
							--sz;
						}
						line.push_back(x);
						return;
					}
					
					void add_line(LL a , LL b , int id){
						insert_line(Line(a , b , id));
						return;
					}
					
					pair<LL,int> Find(LL val){
						int sz = line.size();
						while (p < sz && (p==0 || compare2(line[p - 1] , line[p] , val))) ++p;
						p = min(p , sz);
						--p;
						return {F(line[p] , val) , line[p].id};
					}
		};
		Convex_Hull cover[MAXK + 2];
		
	void main_code(){
		for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
		++k;
		int turn = 0;
		cover[0].add_line(0 , 0 , 0);
		for(int i = 1; i <= n; ++i){
			turn = !turn;
			for (int used = k; used >= 1; --used){
				if (cover[used - 1].line.size() == 0) continue;
				pair<LL,int> kq = cover[used - 1].Find(pre[i]);
				dp[turn][used] = kq.first - pre[i] * pre[i] + pre[n] * pre[i];
				trace[i][used] = kq.second;
				cover[used].add_line(pre[i] , dp[turn][used] - pre[n] * pre[i] , i);
			}
		}
		cout << dp[turn][k] << '\n';
		vector<int>border;
		while (n){
			border.push_back(n);
			n = trace[n][k] , --k;
		}
		reverse(border.begin() , border.end());
		border.pop_back();
		for(auto& x : border) cout << x << ' '; 	
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ; 
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}	

		cin >> n >> k;
		for(int i = 1; i <= n; ++i) cin >> a[i];

		if (subtask2::check()) return subtask2::main_code() , 0;
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:126:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:127:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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