Submission #857897

#	Time	Username	Problem	Language	Result	Execution time	Memory
857897		nammm	Split the sequence (APIO14_sequence)	C++14	0 / 100	69 ms	4748 KiB

sequence

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define vi vector<int>
using namespace std;
const int N=1e5+5;
int par[25][N]{0};
int d1[N]{0},d2[N]{0};
int a[N]{0};
int n;
int cur=1;
void solve(int l,int r,int opl,int opr){
    int m=(l+r)>>1;
    pii t = {0,0};
    for(int i=opl;i<=min(opr,m-1);i++){
        t=max(t,{d1[i]+(a[m]-a[i])*(a[n]-a[m]),i});
    }
    par[cur][m]=t.s;
    d2[m]=t.f;
    if(l>=r)return;
    solve(l,m-1,opl,t.s);
    solve(m+1,r,t.s,opr);

}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=k;i++){
        solve(1,n,0,n);
        for(int i=1;i<=n;i++)d1[i]=d2[i];
        cur++;
    }int ans=0;
    int mem;
    for(int i=1;i<=n;i++){
        if(ans<d2[i])ans=d2[i],mem=i;
    }
    cout<<ans<<"\n";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37:9: warning: variable 'mem' set but not used [-Wunused-but-set-variable]
   37 |     int mem;
      |         ^~~

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