Submission #37554

#	Time	Username	Problem	Language	Result	Execution time	Memory
37554		Talant	Split the sequence (APIO14_sequence)	C++11	100 / 100	1116 ms	82880 KiB

sequence

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)1e5 + 7;

ll dp[2][N];
ll p[N];
int pr[201][N];
int n;

inline ll calc (int r,int l) {
        return p[l] * (p[r] - p[l]);
}
inline int min(int a, int b)
{
        return a < b ? a : b;
}
void compute (int k,int l,int r,int L,int R) {

        if (l > r) return;

        int m = (l + r) >> 1;

        dp[k & 1][m] = 0;

        int &opt = pr[k][m];

        for (int i = L; i <= min(m - 1,R); i ++) {

                ll now = dp[k & 1 ^ 1][i] + calc(m,i);

                if (now >= dp[k & 1][m]) {
                        dp[k & 1][m] = now;
                        opt = i;
                }
        }
        compute (k, l,m - 1, L, opt);
        compute (k, m + 1, r, opt, R);
}

int kk;
main () {
        scanf ("%d%d", &n,&kk);

        for (int i = 1; i <= n; i ++) {
                scanf ("%lld", &p[i]);
                p[i] += p[i - 1];
        }

        for (int i = 1; i <= kk; i ++)
                compute (i,1,n,1,n - 1);

        printf("%lld\n", dp[kk & 1][n]);


        while (kk > 0) {
               printf("%d ", pr[kk][n]);
                n = pr[kk][n];
                kk --;
        }
}
/**
7 3
4 1 3 4 0 2 3
**/

Compilation message (stderr)

sequence.cpp: In function 'void compute(int, int, int, int, int)':
sequence.cpp:33:31: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                 ll now = dp[k & 1 ^ 1][i] + calc(m,i);
                               ^
sequence.cpp: At global scope:
sequence.cpp:45:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
sequence.cpp: In function 'int main()':
sequence.cpp:46:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d%d", &n,&kk);
                               ^
sequence.cpp:49:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%lld", &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