Submission #1187229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187229		Malix	Split the sequence (APIO14_sequence)	C++20	33 / 100	3 ms	2632 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);
    int n,m;cin>>n>>m;
    vector<ll> a(n);
    vector<vector<ll>> dp(n,vector<ll>(m+1,0));
    vii p(n,vi(m+1));
    REP(i,0,n)cin>>a[i];
    REP(j,1,m+1){
        int pos=j-1;
        ll x=0,y=0;
        REP(i,0,j)x+=a[i];
        REP(i,j,n){
            y+=a[i];
            dp[i][j]=dp[pos][j-1]+x*y;
            p[i][j]=pos;
            while(pos+1<i&&dp[i][j]<=dp[pos+1][j-1]+(x+a[pos+1])*(y-a[pos+1])){
                pos++;
                x+=a[pos];
                y-=a[pos];
                dp[i][j]=dp[pos][j-1]+x*y;
                p[i][j]=pos;
            }
        }
    }
    cout<<dp[n-1][m]<<"\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: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29