Submission #1178561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178561		peteza	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	328 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll neginf = -1e18;

struct Line {
    ll m, c;
    int cutidx = 0;
    ll operator()(ll x) {return m*x+c;}
    Line(ll _m, ll _c): m(_m), c(_c) {}
};

ll floordiv(ll a, ll b) {
    return a/b - ((a^b) < 0 && a%b);
}

bool bruh(Line old1, Line old2, Line toins) {
    //check if u should del or not
    if(toins.m == old2.m) return toins.c >= old2.c;
    return floordiv(toins.c - old1.c, old1.m - toins.m) <= floordiv(old1.c - old2.c, old2.m - old1.m);
}

int n, k;
ll qs[200005];
ll dp[200005][2];
int par[20005][205];

void rec(int x, int k) {
    if(x == 0) return ;
    rec(par[x][k], k-1);
    if(par[x][k]) cout << par[x][k] << ' ';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> k;
    for(int i=1;i<=n;i++) {
        cin >> qs[i];
        qs[i] += qs[i-1];
    }
    for(int ck=2;ck<=k+1;ck++) {
        for(int i=0;i<=n;i++) dp[i][ck&1] = neginf;
        deque<Line> deq;
        for(int ci=ck-1;ci<n;ci++) {
            Line toins(qs[ci], dp[ci][(ck&1)^1] - qs[ci]*qs[ci]); toins.cutidx = ci;
            while(deq.size() > 1 && bruh(deq[deq.size()-2], deq.back(), toins)) deq.pop_back();
            deq.emplace_back(toins);
            while(deq.size() > 1 && deq[0](qs[ci+1]) <= deq[1](qs[ci+1])) deq.pop_front();
            dp[ci+1][ck&1] = deq[0](qs[ci+1]);
            par[ci+1][ck] = deq[0].cutidx;
        }
    }
    cout << dp[n][(k&1)^1] << '\n';
    rec(n, k+1);

}

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