Submission #838948

#	Time	Username	Problem	Language	Result	Execution time	Memory
838948		TrinhKhanhDung	Split the sequence (APIO14_sequence)	C++14	100 / 100	891 ms	82888 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)x.size()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(k) (1LL << (k))
#define fi first
#define se second
#define v1 vector<unsigned int>
#define v2 vector<v1>
#define INF (int)(1e9)
#define lim (int)(1000000)
#define MAX (int)(100003)
#define MAX_K (int)(203)
#define MOD (ll)(1000000007)

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template <class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template <class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

using namespace std;

int N, K;
int a[MAX], trace[MAX][MAX_K];
ll pre[MAX], f[2][MAX];

ll w(int l, int r, ll f[])
{
    return f[l-1] + pre[l-1] * (pre[r] - pre[l-1]);
}

struct Info
{
    int p, l, r;
};

void Solve(int k, ll g[], ll f[])
{
    deque<Info> st;
    st.push_back({1, 1, N});
    for(int i=1; i<=N; i++){
        f[i] = w(st.front().p, i, g);
        trace[i][k] = st.front().p - 1;

        if(i == N) break;
        if(st.front().r == i) st.pop_front();
        else st.front().l++;

        while(!st.empty() && w(i + 1, st.back().l, g) >= w(st.back().p, st.back().l, g)) st.pop_back();

        if(st.empty()) st.push_back({i + 1, i + 1, N});
        else {
            int l = st.back().l, r = st.back().r, id;
            while(l <= r){
                int m = (l + r) >> 1;
                if(w(i + 1, m, g) < w(st.back().p, m, g)){
                    id = m;
                    l = m + 1;
                } else r = m - 1;
            }
            st.back().r = id;
            if(id < N) st.push_back({i + 1, id + 1, N});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

//    freopen("sequence.in", "r", stdin);
//    freopen("sequence.out", "w", stdout);

    cin >> N >> K;
    for(int i=1; i<=N; i++){
        cin >> a[i];
        pre[i] = pre[i-1] + 1ll * a[i];
    }

    K++;
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    for(int i=1; i<=K; i++){
        Solve(i, f[!(i & 1)], f[i & 1]);
    }

    cout << f[K & 1][N] << '\n';

    stack<int> ans;

    int u = N;
    for(int i=K; i>1; i--){
        u = trace[u][i];
        ans.push(u);
    }

    while(!ans.empty()){
        cout << ans.top() << ' ';
        ans.pop();
    }

    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void Solve(int, long long int*, long long int*)':
sequence.cpp:69:48: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |             if(id < N) st.push_back({i + 1, id + 1, N});
      |                                             ~~~^~~

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