Submission #498471

#	Time	Username	Problem	Language	Result	Execution time	Memory
498471		xynex	Split the sequence (APIO14_sequence)	C++17	100 / 100	581 ms	82528 KiB

sequence

/*
* Author: xynex
* Created: 25.12.2021 14:00
* Why am I so stupid? :c
* Slishkom slab
*/

#include <bits/stdc++.h>

 #pragma GCC optimize("inline")
 #pragma GCC optimize("-fgcse,-fgcse-lm")
 #pragma GCC optimize("-ftree-pre,-ftree-vrp")
 #pragma GCC optimize("-ffast-math")
 #pragma GCC optimize("-fipa-sra")
 #pragma GCC optimize("-fpeephole2")
 #pragma GCC optimize("-fsched-spec")
 #pragma GCC optimize("Ofast,no-stack-protector")
 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 #pragma GCC optimize("unroll-loops")

using namespace std;

#define ll long long
const int N = 1e5 + 1;
const int M = 201;
const ll INF = 1e9;

ll dp[N][2], pref[N];
int path[N][M];
int n, k;
bool get(ll x, ll y, ll z) {
    ll ind = dp[y][0] - dp[x][0];
//    print(ind);
    ll ind1 = (pref[n] - pref[z]) * (pref[y] - pref[x]);
//    print(ind1);
    return ind >= ind1;
}
bool get1(ll x, ll y, ll z) {
    ll ind = dp[y][0] - dp[x][0];
    ind *= pref[z] - pref[y];
//    print(ind);
    ll ind1 = dp[z][0] - dp[y][0];
    ind1 *= pref[y] - pref[x];
//    print(ind1);
    return ind <= ind1;
}
void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> pref[i];
        pref[i] += pref[i - 1];
    }
    vector<ll> d(n + 1);
    for(int i = 1; i <= k; ++i) {
        d[0] = 0, d[1] = 0;
        int l = 0, r = 1;
        for(int j = 1; j <= n; ++j) {
            while(r - l > 1 && get(d[l], d[l + 1], j)) l++;
            int pos = d[l];
            if(dp[pos][0] + (pref[n] - pref[j]) * (pref[j] - pref[pos]) >= dp[j][1]) {
                dp[j][1] = dp[pos][0] + (pref[n] - pref[j]) * (pref[j] - pref[pos]);
                path[j][i] = pos;
            }
            while(r - l > 1 && get1(d[r - 2], d[r - 1], j)) r--;
            d[r] = j;
            r++;
//            print(d);
        }
        for(int j = 1; j <= n; ++j) dp[j][0] = dp[j][1], dp[j][1] = 0;
    }
//    for(int i = 1; i <= k; ++i) {
//        print(i);
//        for(int j = 1; j <= n; ++j) write(dp[j][i], ' ');
//        print("");
//    }
    int whr = 0;
    ll mx = -INF;
    for(int i = 1; i <= n; ++i) {
        if(mx < dp[i][0]) {
            mx = dp[i][0];
            whr = i;
        }
    }
    cout << mx << "\n";
    for(int i = 1; i <= k; ++i) {
        cout << whr << " ";
        whr = path[whr][k - i + 1];
    }
}

int main() {
    //freop("");
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //read(t);
    for (int i = 1; i <= t; ++i) {
        //write("Case #" + to_string(i) + ": ");
        solve();
    }
    return 0;
}

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