Submission #1187377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187377		Malix	Split the sequence (APIO14_sequence)	C++20	100 / 100	673 ms	89088 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int main() {   
// ios::sync_with_stdio(0);
// // cin.tie(0);
// freopen("test_input.txt", "r", stdin);
// freopen("test_output.txt", "w", stdout);
    int n,m;cin>>n>>m;
    vector<ll> a(n,0);
    vector<vector<ll>> dp(n,vector<ll>(2,0));
    vii p(n,vi(m+1));
    REP(i,0,n)cin>>a[i];
    REP(i,1,n)a[i]+=a[i-1];
    deque<int> q;
    REP(j,1,m+1){
        q.clear();
        q.push_back(j-1);
        REP(i,j,n){;
            while(q.size()>1&&dp[q[0]][0]+(a[i]-a[q[0]])*a[q[0]]<=dp[q[1]][0]+(a[i]-a[q[1]])*a[q[1]])q.pop_front();
            dp[i][1]=dp[q[0]][0]+(a[i]-a[q[0]])*a[q[0]];
            p[i][j]=q[0];
            int sz=q.size();
            while(sz>1&&(dp[i][0]-a[i]*a[i]-dp[q[sz-1]][0]+a[q[sz-1]]*a[q[sz-1]])*(a[q[sz-2]]-a[q[sz-1]])<=(dp[q[sz-1]][0]-a[q[sz-1]]*a[q[sz-1]]-dp[q[sz-2]][0]+a[q[sz-2]]*a[q[sz-2]])*(a[q[sz-1]]-a[i])){
                q.pop_back();
                sz--;
            }
            q.push_back(i);
        }
        REP(i,0,n)dp[i][0]=dp[i][1];
    }
    cout<<dp[n-1][1]<<"\n";
    int x=n-1;
    for(int j=m;j>=1;j--){
        cout<<p[x][j]+1<<" ";
        x=p[x][j];
    }
}

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