Submission #1000817

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

sequence

/**
 *    hello
 *    author:  N29
 *    created: 2024-06-15 09:16:01
**/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e5+100;
const int M=5001;
const int B=447;
const int mod=998244353;
const ll INF=1e9;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;
inline namespace _LineContainer {
bool _Line_Comp_State;
struct Line {
	mutable ll k, m, p;
	bool operator<(const Line &o) const {
		return _Line_Comp_State ? p < o.p : k < o.k;
	}
};

struct LineContainer : multiset<Line> {
	long long div(long long a, long long b) {
		return a / b - ((a ^ b) < 0 && a % b);
	}

	bool isect(iterator x, iterator y) {
		if (y == end()) {
			x->p = LLONG_MAX;
			return false;
		}
		if (x->k == y->k) x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}

	void add(long long k, long long m) {
		auto z = insert({k, m, 0}), 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));
	}

	long long query(long long x) {
		assert(!empty());
		_Line_Comp_State = 1;
		auto l = *lower_bound({0, 0, x});
		_Line_Comp_State = 0;
		return l.k * x + l.m;
	}
};
}
LineContainer lc;
struct line{
    int m,c;
    
    int eval(int x){
        return m*x+c;
    }
    ld inter(line l){
        return (ld)(c-l.c)/(l.m-m);
    }
};
int n,k;
int a[N];
int dp[201][N];
int p[201][N];
int pref[N];
deque<line>q;
bool check(line x,line y,line z){
    return (z.c-x.c)*(x.m-y.m)<=(y.c-x.c)*(x.m-z.m);
}

void add(int m,int b){
    line x={m,b};
    while(q.size()>=2&&check(q[q.size()-2],q.back(),x)){
        q.pop_back();
    }
    q.push_back(x);
}
int query(int x){
    while(q.size()>=2&&q[0].eval(x)<=q[1].eval(x)){
        q.pop_front();
    }
    return q.front().eval(x);
}
void test(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pref[i]=pref[i-1]+a[i];
    }
    // k++;
    for(int i=1;i<=k;i++){    
        q.clear();
        for(int j=i;j<=n;j++){
            // lc.add(pref[j-1],dp[i-1][j-1]-pref[j-1]*pref[j-1]);
            add(pref[j-1],dp[i-1][j-1]-pref[j-1]*pref[j-1]);
            dp[i][j]=query(pref[j]);
        }
    }
    vector<int>v;
    int cur=n;
    for(int i=k-1;i>=0;i--){
        for(int j=cur;j>=1;j--){
            int d=dp[i][j-1]+pref[j-1]*(pref[cur]-pref[j-1]);
            if(dp[i+1][cur]==d){
                cur=j-1;
                v.push_back(j-1);
                break;
            }
        }
    }
    // for(int i=1;i<=k;i++){    
    //     for(int j=1;j<=n;j++){
    //         cout<<dp[i][j]<<' ';
    //     }
    //     cout<<'\n';
    // }
    cout<<dp[k][n]<<'\n';
    reverse(v.begin(),v.end());
    for(auto i:v){
        cout<<i<<' ';
    }
    cout<<'\n';
   


}



/*

*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    int t2=1;
    // cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
}

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