제출 #785257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785257		coding_snorlax	Split the sequence (APIO14_sequence)	C++14	22 / 100	37 ms	4332 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<ll> List={};
vector<ll> prefix={0};
ll dp[52][52][52]={{{0}}};
ll back_track[52][52][52][2];
// dp[i][j][k] : from i to j cut k times max answer
//vector<int> answer;
void Find_answer(int i,int j,int k){
    //cout << i << " " << j << " " << k << "\n";
    if(k==0) return;
    cout << back_track[i][j][k][0]+1 << " ";
    //answer.push_back(back_track[i][j][k][0]+1);
    Find_answer(i,back_track[i][j][k][0],back_track[i][j][k][1]);
    Find_answer(back_track[i][j][k][0]+1,j,k-back_track[i][j][k][1]-1);
}

int main(){
    ll N,K;
    cin>>N>>K;
    for(int i=0;i<N;i++){
        ll num;
        cin>>num;
        List.push_back(num);
        prefix.push_back(prefix.back()+num);
    }
    for(int k=1;k<=K;k++){
        for(int i=0;i<N;i++){
            for(int j=i;j<N;j++){
                ll Max = 0;
                for(int l=i;l<=j;l++){
                    for(int c=0;c<k;c++){
                        if(l-i>=c & j-l-1>=k-c-1){
                            ll tmp = dp[i][l][c]+dp[l+1][j][k-c-1]+(prefix[l+1]-prefix[i])*(prefix[j+1]-prefix[l+1]);
                            if(tmp>Max){
                                Max = tmp ;
                                back_track[i][j][k][0]=l;
                                back_track[i][j][k][1]=c;
                            }
                        }
                    }
                }
                dp[i][j][k]=Max;

                //cout << "i " << i << "j " << j << "k " << k << " " << dp[i][j][k]<<"\n";
            }
        }
    }
    cout<<dp[0][N-1][K]<<"\n";
    Find_answer(0,N-1,K);
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:34:31: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   34 |                         if(l-i>=c & j-l-1>=k-c-1){
      |                            ~~~^~~

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