Submission #46330

#	Time	Username	Problem	Language	Result	Execution time	Memory
46330		top34051	Split the sequence (APIO14_sequence)	C++17	49 / 100	2067 ms	83964 KiB

sequence

//noey power
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int n,m;
ll a[maxn], sum[maxn];
ll dp[maxn][2];
int rec[maxn][205];
void solve(int k, int l, int r, int bl, int br) {
    if(l>r) return ;
    int x = (l+r)/2;
    rec[x][k] = dp[x][k&1] = 0;
    for(int y=max(k-1,bl);y<=min(x-1,br);y++) {
        ll t = dp[y][!(k&1)] + sum[y]*(sum[x]-sum[y]);
        if(t > dp[x][k&1]) {
            dp[x][k&1] = t;
            rec[x][k] = y;
        }
    }
    solve(k,l,x-1,bl,rec[x][k]); solve(k,x+1,r,rec[x][k],br);
}
void go(int x, int k) {
    if(x==0) return ;
    go(rec[x][k], k-1);
    if(x!=n) printf("%d ",x);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + a[i];
    for(int k=1;k<=m;k++) solve(k,1,n,0,n-1);
    printf("%lld\n",dp[n][m&1]);
    go(n,m);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:30:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
                           ~~~~~^~~~~~~~~~~~~~

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