Submission #1260320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260320		LucasLe	Split the sequence (APIO14_sequence)	C++17	71 / 100	144 ms	168792 KiB

sequence

#include <bits/stdc++.h>
 
 #define int long long
const int maxn = 1e5 + 5;
const long long INF = 1e18;
 
int n, k;
int trace[maxn + 5][205];
int a[maxn + 5], pref[maxn + 5];
long long f_prev[maxn + 5], f[maxn + 5];
 
long long divi(long long x, long long y) {
        if (!x || !y) return 0ll;
        return x / y - ((x ^ y) < 0 && x % y);
}
 
struct line {
        int pos;
        long long a, b;
        line(long long _a, long long _b, int _pos) : a(_a), b(_b), pos(_pos) {}
        long long operator () (long long x) { return a * x + b; }
        long long intersect(const line &other) {
                return divi(other.b - b, a - other.a);
        }
};

bool check(line l1, line l2, line l3) {
  int b23 = l3.b - l2.b;
  int a23 = l2.a - l3.a;

  int b12 = l2.b - l1.b;
  int a12 = l1.a - l2.a;

  if (a23 < 0) {
    b23 *= -1;
    a23 *= -1;
  }

  if (a12 < 0) {
    b12 *= -1;
    a12 *= -1;
  }

  return b23 * a12 >= b12 * a23;
}

bool check_intersect(line l1, line l2, int x) {
  int b12=(l2.b-l1.b);
  int a12=(l1.a-l2.a);
  if(a12<0){
    a12*=-1;
    b12*=-1;
  }
  return b12<x*a12;
}
 
struct CHT {
        std::vector<line> data_line;
        
        void add(line d) {
                while ((int)data_line.size() >= 2 &&
                check(data_line[(int)data_line.size() - 2], data_line[(int)data_line.size() - 1], d)) {
                        data_line.pop_back();
                }
                data_line.push_back(d);
        }
 
        int query(long long x) {
                int l = 0, r = (int)data_line.size() - 1, pos;
                while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (!mid) {
                          pos=mid;
                          l=mid+1;
                          continue;
                        }
                        if (check_intersect(data_line[mid], data_line[mid - 1], x)) {
                                r = mid - 1;
                        } else {
                                l = mid + 1;
                                pos = mid;
                        }
                }
                line d = data_line[pos];
                return d.pos;
        }
};
 
void solve() {
        std::cin >> n >> k;
        for (int i = 1; i <= n; ++i) std::cin >> a[i];
        for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i];
 
        for (int i = 1; i < n; ++i)
                f_prev[i] = 1ll * (pref[n] - pref[i]) * pref[i];
 
        int pos_ans;
        long long ans = -1;        
 
        if (k == 1) {
                for (int i = 1; i < n; ++i)
                        if (ans < f_prev[i]) {
                                ans = f_prev[i];
                                pos_ans = i;
                        }
                std::cout << ans << '\n';
                std::cout << pos_ans;
                return;
        }
 
        for (int j = 2; j <= k; ++j) {
                CHT lc;
                for (int i = j; i < n; ++i) {
                        // f[i][j] = (pref[i] - pref[l]) * (pref[n] - pref[i]) + f[l][j - 1];
                        //         = (pref[n] - pref[i]) * pref[i] - (pref[n] - pref[i]) * pref[l] + f[l][j - 1];
                        lc.add(line(1ll * -pref[i - 1], f_prev[i - 1], i - 1));
                        int pos = lc.query(1ll * pref[n] - pref[i]);
                        f[i] = 1ll * (pref[n] - pref[i]) * pref[i] + 1ll * -pref[pos] * (pref[n] - pref[i]) + f_prev[pos];
                        trace[i][j] = pos;
                        if (j == k) {
                                if (ans < f[i]) {
                                        ans = f[i];
                                        pos_ans = i;
                                }
                        }
                }
                for (int i = 1; i < n; ++i) f_prev[i] = f[i];
        }
 
        std::vector<int> pos_vec;
        while (k) {
                assert(pos_ans > 0);
                pos_vec.push_back(pos_ans);
                pos_ans = trace[pos_ans][k];
                k--;
        }
        
        reverse(pos_vec.begin(), pos_vec.end());
        std::cout << ans << '\n';
        for (int x : pos_vec) std::cout << x << ' ';
}
 
signed main() {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(0);
 
        int tc = 1;
        // std::cin >> tc;
        while (tc--)
                solve();
}

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