Submission #716862

#	Time	Username	Problem	Language	Result	Execution time	Memory
716862		vjudge1	Split the sequence (APIO14_sequence)	C++17	71 / 100	63 ms	131072 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e6 + 100;
const int mod = (int)1e9+7;
int n, k;
int a[maxn];
ll pref[maxn];
ll d[maxn];
ld inter(int i, int j) {

    return (ld)(d[j] - d[i])/(pref[i] - pref[j]);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }
    vector< vector<ll> > dp(n + 1, vector<ll>(k+1, 0));
    vector< vector<int> > p(n + 1, vector<int>(k+1, 0));
    
    for(int i = 1; i <= n; i++) {
        dp[i][0] = 0;
    }
    for(int it = 1; it <= k; it++) {
        int j = 0;
        for(int i = 0; i <= n; i++) {
            d[i] = dp[i][it-1]  - pref[i]*pref[i];
        }
        vector<int> st;
        st.push_back(0);
        for(int i = 1; i <= n; i++) {
            if(j >= st.size()) {
                j = (int)st.size() - 1;
            }
            while(j + 1 < st.size() && d[st[j]] + pref[i] * pref[st[j]] <= d[st[j+1]] + pref[i] * pref[st[j+1]]) j++;
            int t = st[j];
            p[i][it] = t;
            dp[i][it] = pref[t] * pref[i] + d[t];
            int sz = (int)st.size();
            while(sz > 0 && pref[i] == pref[st[sz-1]]) {
                st.pop_back();
                sz--;
            }
            while(sz > 1 && inter(st[sz - 1], st[sz-2]) > inter(i, st[sz-2])) {
                st.pop_back();
                sz--;
            }
            st.push_back(i);
        }

    }
    vector<int> cur;
    int last = n;

    for(int i = k; i >= 1; i--) {
        last = p[last][i];
        cur.push_back(last);
    }
    cout << dp[n][k] << "\n";
    reverse(cur.begin(), cur.end());
    for(int x: cur) cout << x << " ";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if(j >= st.size()) {
      |                ~~^~~~~~~~~~~~
sequence.cpp:42:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while(j + 1 < st.size() && d[st[j]] + pref[i] * pref[st[j]] <= d[st[j+1]] + pref[i] * pref[st[j+1]]) j++;
      |                   ~~~~~~^~~~~~~~~~~

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