Submission #1263982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263982		_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 int N = (int) 1e5;
const int MAXK = (int) 200;
	int a[N + 2];
	int n , k;
	
namespace subtask1{
	bool check(){
		return n <= 1000;
	}
	
	const int maxn = (int) 1e3;
		int trace[maxn + 2][MAXK + 2] = {};
		LL dp[maxn + 2][MAXK + 2];
		LL pre[maxn + 2] = {};
		
	void main_code(){
		for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
		memset(dp,-0x3f,sizeof dp);
		dp[0][0] = 0;
		++k;
		for(int i = 1; i <= n; ++i) {
			for(int used = 1; used <= k; ++used){
				for(int t = 0; t < i; ++t) {
					if (maximize(dp[i][used] , dp[t][used - 1] + (pre[n] - pre[i]) * (pre[i] - pre[t]))){
						trace[i][used] = t;
					}
				}
			}
		}
		
		cout << dp[n][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 << ' '; 
	}
}

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) {};
	};
	struct Hull{
		Line x;
		long double intersec;
	};
	
		long double get_intersec(Line x , Line y){
			return (long double)(y.b - x.b) / (long double)(x.a - y.a);
		}
		LL F(Line a , LL x){
			return a.a * x + a.b;
		}
		
		class Convex_Hull{
			public:
				vector<Hull>line;
				
					void insert_line(Line x){
						int sz = sz(line) ;
						while (sz >= 2 && line[sz - 1].intersec >= get_intersec(x , line[sz - 2].x)) {
							line.pop_back();
							--sz;
						}
						if (line.empty()) line.push_back({x , LLONG_MIN});
						else {
							line.push_back({x , get_intersec(line[sz - 1].x , 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 = 0 , high = sz(line) - 1 , p = 0;
						while (low <= high){
							int mid = (low + high) / 2;
							if (line[mid].intersec <= val){
								p = mid;
								low = mid + 1;
							}
							else  high = mid - 1;
						}
						return {F(line[p].x , val) , line[p].x.id};
					}
		};
	
		
		Convex_Hull cover[MAXK + 2];
		
	void main_code(){
		for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
		int turn = 0;
		memset(dp[turn] , -0x3f , sizeof dp[turn]);
		cover[0].add_line(0 , 0 , 0);
		++k;
		for(int i = 1; i <= n; ++i){
			turn = !turn;
			memset(dp[turn] , -0x3f , sizeof dp[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 (subtask1::check()) return subtask1::main_code() , 0;
		if (subtask2::check()) return subtask2::main_code() , 0;
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:170:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:171:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |                         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