Submission #1113670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113670		LucasLe	Split the sequence (APIO14_sequence)	C++17	100 / 100	1399 ms	90628 KiB

sequence

#include <bits/stdc++.h>
 
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);
        }
};
 
struct CHT {
        std::vector<std::pair<line, long long>> data_line;
        
        void add(line d) {
                while (!data_line.empty() &&
                d.intersect(data_line.back().first) >= data_line.back().second) {
                        data_line.pop_back();
                }
                if (data_line.empty())
                        data_line.push_back({d, INF});
                else
                        data_line.push_back({d, d.intersect(data_line.back().first)});
        }
 
        int query(long long x) {
                int l = 0, r = (int)data_line.size() - 1, pos;
                while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (data_line[mid].second < x) {
                                r = mid - 1;
                        } else {
                                l = mid + 1;
                                pos = mid;
                        }
                }
                line d = data_line[pos].first;
                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 << ' ';
}
 
int main() {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(0);
 
        int tc = 1;
        // std::cin >> tc;
        while (tc--)
                solve();
}

Compilation message (stderr)

sequence.cpp: In constructor 'line::line(long long int, long long int, int)':
sequence.cpp:18:22: warning: 'line::b' will be initialized after [-Wreorder]
   18 |         long long a, b;
      |                      ^
sequence.cpp:17:13: warning:   'int line::pos' [-Wreorder]
   17 |         int pos;
      |             ^~~
sequence.cpp:19:9: warning:   when initialized here [-Wreorder]
   19 |         line(long long _a, long long _b, int _pos) : a(_a), b(_b), pos(_pos) {}
      |         ^~~~
sequence.cpp: In function 'void solve()':
sequence.cpp:51:39: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |                 line d = data_line[pos].first;
      |                                       ^
sequence.cpp:41:59: note: 'pos' was declared here
   41 |                 int l = 0, r = (int)data_line.size() - 1, pos;
      |                                                           ^~~

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