Submission #23267

#	Time	Username	Problem	Language	Result	Execution time	Memory
23267		top34051	Split the sequence (APIO14_sequence)	C++14	100 / 100	1503 ms	84836 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int n,k;
int p[maxn];
long long sum[maxn];
long long mem[2][maxn];
int track[205][maxn];
void f(int now,int l,int r,int posl,int posr)
{
    if(l>r) return ;
    int i,x;
    long long t;
    x = (l+r)/2;
    mem[now%2][x] = -1;
    for(i=max(x,posl);i<=posr;i++)
    {
        t = mem[(now-1)%2][i+1] + (sum[x]-sum[i+1])*sum[i+1];
        if(t>mem[now%2][x])
        {
            mem[now%2][x] = t;
            track[now][x] = i;
        }
    }
    f(now,l,x-1,posl,track[now][x]);
    f(now,x+1,r,track[now][x],posr);
}
void g(int now,int x)
{
    if(now<=0) return ;
    printf("%d ",track[now][x]);
    g(now-1,track[now][x]+1);
}
main()
{
    int i;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++) scanf("%d",&p[i]);
    for(i=n;i>=1;i--) sum[i] = sum[i+1] + p[i];
    for(i=1;i<=k;i++) f(i,1,n,1,n);
    printf("%lld\n",mem[k%2][1]);
    g(k,1);
}

Compilation message (stderr)

sequence.cpp:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
sequence.cpp: In function 'int main()':
sequence.cpp:37:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
                        ^
sequence.cpp:38:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%d",&p[i]);
                                        ^

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