Submission #989667

#	Time	Username	Problem	Language	Result	Execution time	Memory
989667		vjudge1	Split the sequence (APIO14_sequence)	C++17	100 / 100	672 ms	83796 KiB

sequence

//這世界上沒有什麼是永恆不變的，只有我和我的自我
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define ii int
#define pb push_back
#define fi first
#define se second
#define Op operator
#define bp __builtin_popcount
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define nn cout<<"NO"<<endl;
#define yy cout<<"YES"<<endl;
#define rep() for(ll i=1 ; i<=n ; i++) cin>>a[i];
#define End() for(ll i=1 ; i<=n ; i++) cout<<a[i]<<" ";
#define TT ll tt;cin>>tt;while(tt--){Test_Case();}
#define T Test_Case() ;
using namespace std;
const ii N = 1e5 , M = 1e6 , mod = 1e9 + 7 , Ones = 1 , Zero = 0;
const ll oo = 1e18 ;
ii a[N + 5] , trace[N + 5][205] ;
ll dp[N + 5][2] , Pre[N + 5] ;
void Calc(ii l , ii r , ii x , ii y , ii k) {
    if(l > r) return ;
    ii mid = l + r >> 1 , op = 0 ;
    for(ii i = x ; i <= min(y , mid - 1) ; i ++ ) {
        if(dp[mid][1] <= Pre[i] * (Pre[mid] - Pre[i]) + dp[i][0]) {
            dp[mid][1] = Pre[i] * (Pre[mid] - Pre[i]) + dp[i][0]; op = i ;
        }
    }
    trace[mid][k] = op ;
    Calc(l , mid - 1 , x , op , k) ; Calc(mid + 1 , r , op , y , k) ;
}
void Test_Case(){
    ii n , k ; cin >> n >> k ;
    for(ii i = 1 ; i <= n ; i ++) {
        cin >> a[i] ; Pre[i] = Pre[i - 1] + a[i] ;
    }
    for(ii i = 1 ; i <= k ; i ++ ) {
        for(ii j = 1 ; j <= n ; j ++) {
            dp[j][0] = dp[j][1] ; dp[j][1] = 0 ;
        }
        Calc(1 , n , 1 , n , i ) ;
    }
    cout << dp[n][1] << endl ;
    vector<ii> ans ; ii now = n ;
    if(dp[n][1] == 0) {
        for(ii i = 1 ; i <= k ; i ++ ) {
            cout << i << " " ;
        }
        return ;
    }
    while(trace[now][k] > 0) {
        ans.pb(trace[now][k]) ; now = trace[now][k -- ] ;
    }
    reverse(ans.begin() , ans.end()) ;
    for(auto & it : ans) cout << it << " " ;
}
int main(){
    Faster
    //freopen("???.inp", "r", stdin);
    //freopen("???.out", "w", stdout);
    T ;
}
////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                Coded by SkyZCoder                                                                                                                                                                                                                                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

Compilation message (stderr)

sequence.cpp: In function 'void Calc(int, int, int, int, int)':
sequence.cpp:28:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     ii mid = l + r >> 1 , op = 0 ;
      |              ~~^~~

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