제출 #46004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46004		sorry_Benq	수열 (APIO14_sequence)	C++17	49 / 100	2062 ms	83872 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
ll S[100005];
ll DP1[100005];
ll DP2[100005];
int BES[100005][205];
const ll INF = 1e18;
 
void fill(int lev, int l, int r, int optl, int optr) {
    if (l > r) return;
    optr = min(optr,r);
    int m = (l+r)/2;
    
    DP2[m] = 1e18;
    int bes = -1;
    FOR(i,optl,min(optr+1,m)) {
        if ((S[m] - S[i])*(S[m] - S[i])+DP1[i]< DP2[m]) {
            DP2[m] = (S[m] - S[i])*(S[m] - S[i])+DP1[i];
            bes = i;
        }
    }
    BES[m][lev] = bes;
    fill(lev, l,m-1,optl,bes);
    fill(lev, m+1,r,bes,optr);
}
 
int main(){
	S[0] = 0;
	int N, K; cin >> N >> K;
	for (int i = 1; i <= N; i++){
		ll x; cin >> x;
		S[i] = S[i - 1] + x;
	}
	for (int i = 1; i <= N; i++){
		DP2[i] = S[i]*S[i];
	}
	for (int j = 2; j <= K + 1; j++){
		for (int i = 1; i <= N; i++){
			DP1[i] = DP2[i];
		}
		fill(j, 1, N, 1, N);
	}
	int curpos = N;
	vector<int> idx; 
	for (int j = K + 1; j >= 2; j--){
		idx.push_back(BES[curpos][j]);
		curpos = BES[curpos][j];
	}
	sort(idx.begin(), idx.end());
	cout << (S[N] * S[N] - DP2[N])/2 << endl;
	for (int j: idx){
		cout << j << ' ';
	}
	cout << endl;
}

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