제출 #1014077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014077		peacebringer1667	수열 (APIO14_sequence)	C++17	11 / 100	21 ms	3164 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
using namespace std;
const int maxn = 53;

struct CTDL{
	int pos = 0,k1 = 0,k2 = 0;
};

ll dp[maxn][maxn][maxn],sum[maxn];
CTDL trace[maxn][maxn][maxn];
inline ll S(int l,int r){
	return sum[r] - sum[l - 1];
}
int a[maxn];

void getdp(int l,int r,int k){
	for (int i = l ; i < r ; i++)
	  for (int k1 = 0 ; k1 < k ; k1++)
	    for (int k2 = 0 ; k2 + k1 < k ; k2++){
	    	ll T = dp[l][r][k1 + k2 + 1];
	    	
	    	ll tmp = dp[l][i][k1] + dp[i + 1][r][k2] + S(l,i)*S(i + 1,r);
	    	if (T < tmp){
	    		dp[l][r][k1 + k2 + 1] = tmp;
	    		trace[l][r][k1 + k2 + 1] = {i,k1,k2};
			}
		}
}

void Trace_back(int l,int r,int k){
	if (!k) return;
	CTDL t = trace[l][r][k];
	
	cout << t.pos << " ";
	Trace_back(l,t.pos,t.k1);
	Trace_back(t.pos + 1,r,t.k2);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    
   // freopen("sequence.in","r",stdin);
  //  freopen("sequence.out","w",stdout);
    
	int n,k;
	cin >> n >> k;
	
	for (int i = 1 ; i <= n ; i++){
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	} 

	for (int len = 1 ; len <= n ; len++)
	  for (int i = 1 ; i <= n - len + 1 ; i++)
	     getdp(i,i + len - 1,k);
	
    cout << dp[1][n][k] << "\n"; 
    Trace_back(1,n,k);
	return 0;
}

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