제출 #36735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
36735		junodeveloper	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	1844 KiB

sequence

#include "bits/stdc++.h"
#define F first
#define S second
#define SZ(x) ((int)x.size())
using namespace std;
template<class T>
struct CHT {
	using pt = pair<T,T>;
	vector<pt> ln;
	vector<int> idx;
	int curr = 0;
	bool bad(pt& a, pt& b, T x) {
		return (b.S - a.S) >= x * (a.F - b.F);
	}
	bool bad(pt& a, pt& b, pt& c) {
		return (b.S - a.S) * (b.F - c.F) >= (c.S - b.S) * (a.F - b.F);
	}
	void insert(pt v, int i) {
		while(SZ(ln) >= 2 && bad(ln[SZ(ln)-2], ln.back(), v))
			ln.pop_back(), idx.pop_back();
		ln.push_back(v), idx.push_back(i);
	}
	pair<T, int> query(T x) {
		assert(SZ(ln) > 0);
		curr = min(curr, SZ(ln) - 1);
		while(curr < SZ(ln) - 1 && bad(ln[curr], ln[curr+1], x))
			curr++;
		return {x * ln[curr].F + ln[curr].S, idx[curr]};
	}
	void clear() {
		ln.clear();
		idx.clear();
		curr = 0;
	}
};
int n, k, s[100010], rec[100010][202];
long long dp[100010][202];
CHT<long long> cht[2];
int main() {
	scanf("%d%d", &n, &k);
	for(int i=1; i<=n; i++) scanf("%d", s+i), s[i] += s[i-1];
	for(int i=1; i<=n; i++)
		cht[0].insert({s[i], -s[i]*s[i]}, i);
	for(int j=2; j<=k+1; j++) {
		cht[(j + 1) % 2].clear();
		for(int i=j; i<=n; i++) {
			tie(dp[i][j], rec[i][j]) = cht[j % 2].query(s[i]);
			cht[(j + 1) % 2].insert({s[i], dp[i][j] - s[i]*s[i]}, i);
		}
	}
	printf("%lld\n", dp[n][k+1]);
	int p = n;
	vector<int> res;
	while(k > 0) {
		res.push_back(rec[p][k+1]);
		p = rec[p][k+1], k--;
	}
	for(int i=SZ(res)-1; i>=0; i--) printf("%d ", res[i]);
	return 0;
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:40:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:41:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d", s+i), s[i] += s[i-1];
                                                          ^

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