제출 #32117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32117		gs14004	수열 (APIO14_sequence)	C++14	11 / 100	2000 ms	4360 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long lint;
typedef pair<lint, int> pi;

int n,k;
lint dp[100005], a[100005];
int trk[100005], cnt[100005];

pi trial(lint x){
	for(int i=1; i<=n; i++){
		dp[i] = -1e18;
		for(int j=0; j<i; j++){
			if(dp[i] < dp[j] + 2 * (a[n] - a[i]) * (a[i] - a[j]) - x){
				dp[i] = dp[j] + 2 * (a[i] - a[j]) * (a[n] - a[i]) - x;
				trk[i] = j;
				cnt[i] = cnt[j] + 1;
			}
		}
	}
	return pi(dp[n], cnt[n]);
}

int main(){
	int t;
	scanf("%d %d",&n,&k);
	for (int i=0; i<n; i++) {
		scanf("%d",&t);
		a[i+1] = a[i] + t;
	}
	lint s = 0, e = 1e13;
	while(s != e){
		lint m = (s+e+1)/2;
		if(trial(m).second >= k+1) s = m;
		else e = m-1;
	}
	cout << (trial(s).first + s * (k+1)) / 2 << endl;
	int p = n;
	vector<int> v;
	for(int j=k; j; j--){
		v.push_back(trk[p]);
		p = trk[p];
	}
	reverse(v.begin(), v.end());
	for(auto &i : v) printf("%d ", i);
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:27:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&k);
                      ^
sequence.cpp:29:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
                 ^

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