Submission #1268317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268317		WH8	Split the sequence (APIO14_sequence)	C++20	22 / 100	4 ms	1352 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 x where this line is best
    int id;                    // label/index
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(long long x) const { return p < x; } // for lower_bound(x)
};

struct LineContainer : std::multiset<Line, std::less<>> {
    static const long long INF = (1LL<<62);

    static long long floordiv(long long a, long long b) {
        long long q = a / b, r = a % b;
        if (r && ((a ^ b) < 0)) --q;
        return q;
    }

    // sets x->p = last x where x is >= y; returns true if x->p >= y->p (y is useless)
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = INF; return false; }
        if (x->k == y->k) {
            // same slope: keep the better intercept; if equal, keep higher id
            if (x->m > y->m || (x->m == y->m && x->id > y->id)) x->p = INF;
            else x->p = -INF;
        } else {
            // last integer x where x is better than y
            x->p = floordiv(y->m - x->m, x->k - y->k);
        }
        return x->p >= y->p;
    }

    // Before inserting, kill worse equal-slope neighbors (keep larger m, tie -> higher id)
    void add(long long k, long long m, int id) {
        Line L{ k, m, 0, id };

        // Remove dominated equal-slope line if present
        auto it = lower_bound(k); // first with slope >= k
        if (it != end() && it->k == k) {
            if (it->m > m || (it->m == m && it->id >= id)) return; // existing is better
            it = erase(it); // new one is >=, so remove old
        } else if (it != begin()) {
            auto it2 = std::prev(it);
            if (it2->k == k) {
                if (it2->m > m || (it2->m == m && it2->id >= id)) return;
                erase(it2);
            }
        }

        auto z = insert(L), 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));
    }

    // Query max at x; if tie on value, prefer higher id.
    std::pair<int,long long> query(long long x) const {
        assert(!empty());
        auto it = lower_bound(x); // best candidate by breakpoints
        long long bestVal = it->k * x + it->m;
        int bestId = it->id;

        // Tie-break check with neighbors: only adjacent lines can tie at a point.
        // Check predecessor
        if (it != begin()) {
            auto pr = std::prev(it);
            long long v = pr->k * x + pr->m;
            if (v == bestVal && pr->id > bestId) {
                bestId = pr->id;
                // bestVal unchanged
            }
        }
        // Check successor
        auto nx = std::next(it);
        if (nx != end()) {
            long long v = nx->k * x + nx->m;
            if (v == bestVal && nx->id > bestId) {
                bestId = nx->id;
            }
        }
        return {bestId, bestVal};
    }
};

// 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;
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));
	hull.add(0, 0, 0);
	int ans=LLONG_MIN,a=0,b=0;
	
	for(int m=1;m<=k;m++){
		LineContainer next;
		for(int i=1;i<=n;i++){
			
			auto [id, best]=hull.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;
			}
			next.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]);
		}
		swap(next, hull);
	}
	cout<<ans<<'\n';
	int ca=a, cb=b,cnt=0;
	while(ca>0 and cb>0){
		cnt++;
		tie(ca,cb)=from[ca][cb];
	}
	assert(cnt==k);
	
	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