Submission #651482

#	Time	Username	Problem	Language	Result	Execution time	Memory
651482		pauloamed	Split the sequence (APIO14_sequence)	C++14	71 / 100	130 ms	131072 KiB

sequence

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 100010;

int S[MAXN], wS[MAXN];

int query(int l, int r){
  int a = S[r];
  int b = S[r] - ((l == 0)? 0 : S[l - 1]);
  int c = wS[r] - ((l == 0)? 0 : wS[l - 1]);
  return a * b - c;
}

int last_dp[MAXN];
int curr_dp[MAXN];

const int MAXK = 250;
pair<int,int> ans[MAXN][MAXK];

int get_dp(int i){
  if(i < 0) return 0;
  else return last_dp[i];
}

int sum(int a, int b){
  if(a == LLONG_MAX) return LLONG_MAX;
  if(b == LLONG_MAX) return LLONG_MAX;
  else return a + b;
}

int K;
void solve(int l, int r, int searchL, int searchR){
  if(l > r) return;
  int j = (l + r) / 2;
  if(curr_dp[j] == -1){
    int validR = min(j, searchR);
    pair<int,int> best = {LLONG_MAX, -1LL};
    for(int k = searchL; k <= validR; ++k){
      int x = sum(query(k, j), get_dp(k - 1));
      if(x <= best.first) best = {x, k};
    }
    curr_dp[j] = best.first;
    ans[j][K] = best;
    solve(l, j - 1, searchL, best.second);
    solve(j + 1, r, best.second, searchR);
  }
}

int32_t main(){
  int n, k; cin >> n >> k;
  vector<int> v(n); for(auto &x : v) cin >> x;

  int tot = 0;
  for(int i = 0; i < n; ++i){
    S[i] = v[i];
    if(i){
      S[i] += S[i - 1];
      tot += v[i] * S[i - 1];
    }
  }

  for(int i = 0; i < n; ++i){
    wS[i] = S[i] * v[i];
    if(i) wS[i] += wS[i - 1];
  }

  // for(int i = 0 ; i < n; ++i){
  //   for(int j = i; j < n; ++j){
  //     cout << i << " " << j << " : " << query(i, j) << "\n";
  //   }
  // }

  for(int i = 0; i < n; ++i){
    last_dp[i] = query(0, i);
  }

  for(K = 0; K < k; ++K){
    memset(curr_dp, -1, sizeof curr_dp);
    solve(0, n - 1, 0, n - 1);
    swap(curr_dp, last_dp);

    // for(int i = 0; i < n; ++i){
    //   cout << i << " : " << ans[i][k].first << " " << ans[i][k].second << "\n";
    // }
    // cout << "=-=-=-=-=-=-\n";
  }

  cout << tot - last_dp[n - 1] << "\n";
  // cout << tot << " " << last_dp[n - 1] << "\n";

  auto curr = make_pair(-1, n);
  for(int i = 0; i < k; ++i){
    curr = ans[curr.second - 1][k - i - 1];
    cout << curr.second << " ";
  }
  cout << "\n";
}

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