제출 #1269229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269229		_rain_	수열 (APIO14_sequence)	C++17	33 / 100	4 ms	1348 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 BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1) << (x))
#define sz(x) (int)(x).size()
#define Time_used cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";

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 T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end()); 
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}

const int N = (int) 1e5;
const LL inf = (LL)1e18;
	int a[N + 2];
	int n , k;
	
	LL pre[N + 2] = {};
	
namespace subtask1{
	bool check(){
		return n <= 200;
	}
	
	const int maxn = 200;
		int trace[maxn + 2][maxn + 2] = {};
		LL dp[maxn + 2][maxn + 2] = {};
	
	void main_code(){
		memset(dp , -0x3f , sizeof dp);
		dp[0][0] = 0;
		++k;
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= i; ++j){
				for(int turn = 1; turn <= k; ++turn){
					LL cc_cost = (pre[i] - pre[j - 1]) * (pre[n] - pre[i]);
					if (maximize(dp[i][turn] , dp[j - 1][turn - 1] + cc_cost)) trace[i][turn] = j - 1;
				}
			}
		}
		
		cout << dp[n][k] << '\n';
		vector<int> ans;
		while(k>0){
			ans.push_back(n);
			n = trace[n][k]; --k;
		}
		reverse(ans.begin() , ans.end());
		ans.pop_back();
		for(auto& x : ans) cout << x << ' '; cout << '\n';
	}
}

namespace subtask2{
	bool check(){
		return true;
	}
	
	struct Line{
		LL a , b;
		int id;
		Line(LL a , LL b , int id) : a(a) , b(b) , id(id) {};
	};
	vector<Line> line;
	
		long double Get_intersec(Line a , Line b){
			return (long double)(b.b - a.b) / (a.a - b.a);
		}
	
	bool compare_1(Line a , Line b , Line c){
		LL x1 = b.a - a.a , x2 = c.a - a.a;
		LL y1 = a.b - b.b , y2 = a.b - c.b;
		return y1 * x2 > y2 * x1;
	}
	
		void insert(Line x){
			int n = sz(line);
			while (n > 1 && compare_1(line[n - 2] , line[n - 1] , x)){
				line.pop_back();
				--n;
			}
			line.push_back(x);
			return;
		}			
		
	bool compare_2(Line a , Line b , LL val){
		LL x1 = b.a - a.a , y1 = a.b - b.b;
		return y1 <= val * x1;
	}
	
	pair<LL,int> F(Line a , LL x){
		return {a.a * x + a.b , a.id};
	}
	
	int ptr = 1;
	
		pair<LL,int> Find(LL x){
			minimize(ptr , sz(line));
			ptr = max(ptr , 1);
			while (ptr < sz(line) && compare_2(line[ptr - 1] , line[ptr] , x)) ++ptr;
			return F(line[ptr - 1] , x);
		}
	
	LL g[N + 2] = {} , dp[N + 2] = {};
	const int MAXK = 200;
	int trace[N + 2][MAXK+2];
	
		void solve(int turn){
			for(int i = 0; i <= n; ++i) dp[i] = -inf;
			line.clear();
			ptr = 1;
			for(int i = 0; i <= n; ++i){
				if (sz(line)){
					pair<LL,int> kq = Find(pre[i]);
					LL cost = kq.first - pre[i] * pre[i] + pre[n] * pre[i];
					dp[i] = cost;
					trace[i][turn] = kq.second;
				}
				if (g[i] != -inf) insert(Line(pre[i] , g[i] - pre[n] * pre[i] , i));
			}
			for(int i = 0; i <= n; ++i) g[i] = dp[i];
			return;
		}
	
	void main_code(){
		++k;
		for(int i = 0; i <= n; ++i) g[i] = -inf;
		g[0] = 0;
		for(int i = 1; i <= k; ++i) {
			solve(i);
		}
		cout << g[n] << '\n';
		vector<int> ans;
		while(k>0){
			ans.push_back(n);
			n = trace[n][k]; --k;
		}
		reverse(ans.begin() , ans.end());
		ans.pop_back();
		for(auto& x : ans) cout << x << ' '; cout << '\n';
	}
}

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];
		for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
		if (subtask1::check()) return subtask1::main_code() , 0;
		return subtask2::main_code() , 0;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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