Submission #989645

#	Time	Username	Problem	Language	Result	Execution time	Memory
989645		khanhtb	Split the sequence (APIO14_sequence)	C++14	100 / 100	959 ms	84572 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7;   
const ll inf = 1e18;
const ll base = 31;
const ll blocksz = 320;
const ll N = 1e5+8;
ll pre[N],dp[N][2];
int trace[N][208];
int n,k;
ll cost(ll l, ll r){
    return (pre[r]-pre[l-1])*pre[l-1];
}
void dnc(int l, int r, int optl, int optr, int j){
    if(l > r) return;
    int m = l+r>>1;
    pll best = {-inf,-1};
    for(ll i = optl; i <= min(m,optr); i++){
        best = max(best,{dp[i-1][(j&1)^1]+cost(i,m),i});
    }
    dp[m][j&1] = best.fi;
    ll opt = best.se;
    trace[m][j] = opt-1;
    dnc(l,m-1,optl,opt,j);
    dnc(m+1,r,opt,optr,j);
}
void solve(){
    cin >> n >> k;
    for(ll i = 1; i <= n; i++){
        ll x;cin >> x;
        pre[i] = pre[i-1]+x;
    }
    for(ll j = 1; j <= k; j++) dnc(1,n,1,n,j);
    cout << dp[n][k&1] << '\n';
    vi ans;
    for(ll i = k; i; i--){
        n = trace[n][i];
        ans.pb(n);
    }
    reverse(all(ans));
    for(ll i:ans) cout << i << " ";
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen("test.inp","r")){
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    // freopen("SSEQ.inp","r",stdin);
    // freopen("SSEQ.out","w",stdout);
    ll T = 1;
    // cin >> T;
    while(T--){
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

sequence.cpp: In function 'void dnc(int, int, int, int, int)':
sequence.cpp:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int m = l+r>>1;
      |             ~^~
sequence.cpp: In function 'int main()':
sequence.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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