Submission #1264050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264050		_rain_	Split the sequence (APIO14_sequence)	C++17	0 / 100	0 ms	328 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[N + 2] = {} , g[N + 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 low = 1 , high = sz(line) - 1 , p = 0;
						while (low <= high){
							int mid = (low + high) / 2;
							if (compare2(line[mid - 1] , line[mid] , val)){
								p = mid;
								low = mid + 1;
							}
							else  high = mid - 1;
						}
						return {F(line[p] , val) , line[p].id};
					}
		};
		
	void solve(int idx){
		for(int i = 0; i <= n; ++i) dp[i] = 0;
		Convex_Hull cover;
		for(int i = 0; i <= n; ++i){
			if (sz(cover.line) && i >= idx){
				pair<LL,int> kq = cover.Find(pre[i]);
				dp[i] = kq.first - pre[i] * pre[i] + pre[n] * pre[i];;
				trace[i][idx] = kq.second;
			}
			cover.add_line(pre[i] , g[i] - pre[n] * pre[i] , i);
		}
		for(int i = 0; i <= n; ++i) g[i] = dp[i];
	}
		
	void main_code(){
		for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
		++k;
		int turn = 0;
		g[0] = 0;
		for(int i = 1; i <= k; ++i) solve(i);
		cout << g[n] << '\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:136:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:137:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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