제출 #43706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43706		baactree	수열 (APIO14_sequence)	C++14	33 / 100	698 ms	83348 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
ll dp[2][100005];
int par[205][100005];
ll sum[100005];
int arr[100005];
pair<ll, ll> dd[100005];
double calc(pair<ll, ll> a, pair<ll, ll> b) {
	return ((double)a.second - b.second) / (b.first - a.first);
}
int main() {
	scanf("%d%d", &n, &k);
	set<int> s;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
		sum[i] = sum[i - 1] + arr[i];
		if (!arr[i])s.insert(i);
	}
	for (int i = 1; i <= k; i++) {
		deque<int> dq;
		int cur = i & 1;
		int pre = (i - 1) & 1;
		for (int j = 1; j <= n; j++) {
			if (!arr[j]) {
				dp[cur][j] = dp[cur][j - 1];
				par[i][j] = par[i][j - 1];
				continue;
			}
			while (dq.size() > 1 && dd[dq[0]].second-dd[dq[1]].second <= sum[j]*(dd[dq[1]].first-dd[dq[0]].first)) 
				dq.pop_front();
			if (!dq.empty()) {
				dp[cur][j] = dd[dq[0]].first * sum[j] + dd[dq[0]].second;
				par[i][j] = dq[0];
			}
			ll a = sum[j];
			ll b = dp[pre][j] - sum[j] * sum[j];
			dd[j] = make_pair(a, b);
			while (dq.size() > 1 && (dd[dq.back()].second-dd[j].second)*(dd[j].first-dd[dq.size()-2].first) <= (dd[dq[dq.size() - 2]].second- dd[j].second)*(dd[j].first-dd[dq.back()].first))
				dq.pop_back();
			dq.push_back(j);
		}
	}
	printf("%lld\n", dp[k&1][n]);
	vector<int> ans;
	while (k) {
		ans.push_back(par[k][n]);
		n = par[k][n];
		k--;
	}
	for (int i = 0; i < ans.size(); i++) {
		s.erase(ans[i]);
		if (!ans[i]) {
			printf("%d ", *s.begin());
			s.erase(s.begin());
		}
		else
			printf("%d ", ans[i]);
	}
	printf("\n");
	return 0;
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                    ^
sequence.cpp:14: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:17:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
                       ^

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