Submission #1122355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122355		yusufhocaoglu	Split the sequence (APIO14_sequence)	C++17	89 / 100	491 ms	89620 KiB

sequence

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl
#define int ll
struct line {
    int x,a,b,i;
    line(int x,int a,int b,int i) : x(a),a(a),b(b),i(i) {}
    int operator()(int x) {return a*x+b;}
};
int intercept(line a,line b) {
    if (a.a == b.a) return -1e9;
    return (b.b-a.b) / (a.a-b.a); //intercepts at x=
}
int32_t main() {
    int n,k;cin>>n>>k;k++;
    vector<vector<int32_t>> goesTO(1e5,vector<int32_t>(200));
    vi a(n);for(int i = 0;i<n;i++) cin>>a[i];
    vi prefix(n);prefix[0]=a[0];for(int i = 1;i<n;i++) prefix[i] = prefix[i-1]+a[i];
    deque<line> stack1;
    deque<line> stack2;
    int cnt = 0;
    int ans;
    while (cnt<k) {
        //using dp1, calc dp2
        stack2.clear();
        stack2.push_back(line(-1e9,0,0,-1));
        for (int i = 0;i<n;i++) {
            //find answer in the previous stack, query x = prefix[i]
            while (stack1.size()>1 && stack1[1].x<prefix[i]) stack1.pop_front();
            ans = stack1.front()(prefix[i]);
            goesTO[i][cnt] = stack1.front().i;
            //we add current line to stack, for future use,
            //y = ans + prefix[i]*prefix[i] + prefix[i]*x
            line now = line(0,+prefix[i],ans-prefix[i]*prefix[i],i);
            while (stack2.size() && intercept(stack2.back(),now) < stack2.back().x) stack2.pop_back();
            stack2.push_back(now);
            if (stack2.size()>1) stack2.back().x = intercept(stack2[stack2.size()-2],stack2.back());
            else stack2.back().x = -1e9;
        }

        swap(stack1,stack2);
        cnt++;
    }
    cout<<ans<<endl;
    int ss = n-1;
    int kn = k-1;
    //cout<<goesTO[ss][kn]<<endl;
    while (ss>-1 && kn>0 && goesTO[ss][kn]!=-1) {
        ss = goesTO[ss][kn];
        kn--;
        cout<<ss+1<<" ";
    }cout<<endl;
    return 0;
}

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