Submission #785280

#	Time	Username	Problem	Language	Result	Execution time	Memory
785280		coding_snorlax	수열 (APIO14_sequence)	C++14	22 / 100	2092 ms	95920 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<ll> List={};
vector<ll> prefix={0};
ll dp[202][202][202]={{{0}}};
ll back_track[202][202][202][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);
}

Compilation message (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