Submission #1104478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104478		BF001	Split the sequence (APIO14_sequence)	C++17	100 / 100	569 ms	82248 KiB

sequence

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

    #define fi first
    #define se second 
    #define N 100005
    #define oo 1e15

    typedef pair<long long, long long> ii;
    typedef pair<long long, pair<long long, long long>> iii;

    
    vector<long long> cur, lst;
     long long pre[N], suf[N];
    int par[201][N], n, k;

    struct cht{
        deque<int> q;
        long long get(int pos, long long x){
            ii tmp = {pre[pos], lst[pos]};
            return tmp.fi * x + tmp.se;
        }
        bool cal(int x, int y, int z){
            ii a = {pre[x], lst[x]};
            ii b = {pre[y], lst[y]};
            ii c = {pre[z], lst[z]};
            return ((long long) 1ll * (c.se - a.se)  * (b.fi - c.fi) >= 1ll * (c.se - b.se) * (a.fi - c.fi));
        }
        void add(long long a, long long b, int pos){
            int nw = pos;
            while ((int) q.size() >= 2 && cal(q[(int)q.size() - 2], q[(int)q.size() - 1], nw)) q.pop_back();
            q.push_back(nw);
        }
        ii get(long long pos){
            if (!(int) q.size()) return {0, 0};
            while ((int) q.size() >= 2 && get(q[0], pos) <= get(q[1], pos)) q.pop_front();
            return {q[0], get(q[0], pos)};
        }
        void reset(){
            q.clear();
        }
    } c1;

   
    
    signed main(){
        ios_base::sync_with_stdio(0);
        cin.tie(NULL);
    
        cin >> n >> k;
        for (int i = 1; i <= n; i++){
            cin >> pre[i];
            pre[i] = pre[i - 1] + pre[i];
        }

        for (int i = 1; i <= n; i++){
            suf[i] = pre[n] - pre[i - 1];
        }
    
        cur.resize(n + 1, 0);
        lst.resize(n + 1, 0);

        for (int i = 1; i <= k; i++){
            lst = cur;
            c1.reset();
            c1.add(pre[i - 1], lst[i - 1], i - 1);
            for (int j = i; j <= n; j++){
                ii gt = c1.get(-suf[j + 1]);
                par[i][j] = gt.fi;
                cur[j] = gt.se + suf[j + 1] * pre[j];
                c1.add(pre[j], lst[j], j);
            }
        }   

        long long res = -oo; int pos = 0, nn = k;
        for (int i = 1; i <= n; i++){
            if (cur[i] > res){
                res = cur[i];
                pos = i;
            }
        }

        vector<int> vec;
        vec.push_back(pos);
        for (int i = k; i >= 2; i--){
            vec.push_back(par[i][pos]);
            pos = par[i][pos];
        }

        sort(vec.begin(), vec.end());
        cout << res << "\n";
        for (auto x : vec) cout << x << " ";

        return 0;
    }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:75:43: warning: unused variable 'nn' [-Wunused-variable]
   75 |         long long res = -oo; int pos = 0, nn = k;
      |                                           ^~

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