Submission #1268314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268314		WH8	Split the sequence (APIO14_sequence)	C++20	22 / 100	6 ms	4424 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'

struct Line {
    mutable long long k, m, p;  // slope, intercept, last optimal x (breakpoint)
    int id;                      // label/index for this line

    // order by slope for the multiset
    bool operator<(const Line& o) const { return k < o.k; }
    // order by x for lower_bound(x) (heterogeneous lookup via less<>)
    bool operator<(long long x) const { return p < x; }
};

// Max hull; for min hull, negate k and/or m appropriately.
struct LineContainer : multiset<Line, less<>> {
    static const long long INF = (1LL<<62); // large sentinel (fits in ll)

    // floored division: floor(a / b), valid for negative a,b as well
    static long long floordiv(long long a, long long b) {
        // b must not be 0
        long long q = a / b;
        long long r = a % b;
        // If signs differ and remainder not zero, floor rounds down (more negative)
        if ((r != 0) && ((a ^ b) < 0)) --q;
        return q;
    }

    // set x->p = intersection point with y; return true if x's breakpoint >= y's
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = INF; return false; }
        if (x->k == y->k) {
            x->p = (x->m > y->m) ? INF : -INF; // keep better line
        } else {
            // ceil division is not needed here; KACTL uses floordiv for max hull
            // Breakpoint is the last x where x is better than y:
            // kx + m >= ky + my  =>  (k - ky) x >= (my - m)
            // x >= (my - m) / (k - ky)
            x->p = floordiv(y->m - x->m, x->k - y->k);
        }
        return x->p >= y->p;
    }

    // insert y = kx + m with label 'id'
    void add(long long k, long long m, int id) {
        auto z = insert({k, m, 0, id}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    }

    // returns {best_id, best_value} at x
    pair<int,long long> query(long long x) const {
        assert(!empty());
        auto l = *lower_bound(x);           // uses Line::<(long long)
        long long val = l.k * x + l.m;
        return {l.id, val};
    }
};

// to use:
// LineContainer hull;
// hull.add(m, c);
// hull.query(x);
// to convert max queries to min queries:
// hull.add(-m, -c);
// -hull.query(x);

LineContainer hull[205];
int n,k;

signed main(){
	cin>>n>>k;
	vector<int> v(n+1,0), p(n+1, 0);
	for(int i=1;i<=n;i++){
		cin>>v[i];
		p[i]=p[i-1]+v[i];
	}
	vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
	vector<vector<pair<int,int>>> from(n+1, vector<pair<int,int>>(k+1));
	for(int m=0;m<=k;m++){
		hull[m].add(0, 0, 0);
	}
	int ans=LLONG_MIN,a=0,b=0;
	
	for(int i=1;i<=n;i++){
		for(int m=k;m>=1;m--){
			auto [id, best]=hull[m-1].query(p[i]);
			int add=-p[i]*p[i]+p[i]*p[n];
			dp[i][m]=best+add;
			from[i][m]={id, m-1};
			if(dp[i][m] > ans){
				ans=dp[i][m];
				a=i,b=m;
			}
			hull[m].add(p[i], dp[i][m]-p[i]*p[n], i);
			//~ printf("i:%lld, splits:%lld, best %lld add %lld\n",i,m,best,add);
			//~ printf("added m=%lld, c=%lld\n", p[i], dp[i][m]-p[i]*p[n]);
		}
	}
	cout<<ans<<'\n';
	while(a>0 and b>0){
		cout<<a<<" ";
		tie(a,b)=from[a][b];
	}
}

/*
4 2
3 1 2 3
*/

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