Submission #197040

#	Time	Username	Problem	Language	Result	Execution time	Memory
197040		mario05092929	Split the sequence (APIO14_sequence)	C++11	100 / 100	1673 ms	81968 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,p[100005];
ll sum[100005],d[2][100005];
int go[205][100005];

void f(int now,int l,int r,int rl,int rr) {
    if(l > r) return;
    int x;
    ll t;
    x = (l + r) >> 1;
    d[now%2][x] = -1;
    for(int i = max(x,rl);i <= rr;i++) {
        t = d[(now+1) % 2][i+1]+(sum[x]-sum[i+1])*sum[i+1];
        if(t > d[now % 2][x]) {
            d[now % 2][x] = t;
            go[now][x] = i;
        }
    }
    f(now,l,x-1,rl,go[now][x]);
    f(now,x+1,r,go[now][x],rr);
}

void printTrack(int now,int x)
{
    if(now == 0) return;
    printf("%d ",go[now][x]);
    printTrack(now-1,go[now][x]+1);
}

int main() {
    scanf("%d %d",&n,&k);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&p[i]);
    }
    for(int i = n;i >= 1;i--) {
        sum[i] = sum[i+1]+p[i];
    }
    for(int i = 1;i <= k;i++) {
        f(i,1,n,1,n);
    }
    printf("%lld\n",d[k%2][1]);
    printTrack(k,1);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         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