Submission #37637

#	Time	Username	Problem	Language	Result	Execution time	Memory
37637		antimirage	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	1840 KiB

sequence

#include <iostream>
#include <vector>
#include <deque>
#include <math.h>
#include <set>
#include <iomanip>
#include <time.h>
#include <list>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <memory.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

const int N = 1e5 + 5;

int n, ar[N], p[205][N];

long long dp[45][N], pref[N];

void compute (int k, int l, int r, int opl, int opr)
{
    if (l > r) return;

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

    int &opt = p[k][md];

    for (int i = opl; i <= min(opr, md - 1); i++)
    {
        if (dp[k & 1 ^ 1][i] + (pref[md] - pref[i]) * (pref[n] - pref[md]) > dp[k & 1][md] )
        {
            dp[k & 1][md] = dp[k & 1 ^ 1][i] + (pref[md] - pref[i]) * (pref[n] - pref[md]);
            opt = i;
        }
    }
    compute( k, l, md - 1, opl, opt );
    compute( k, md + 1, r, opt, opr );
}

int k;

main ()
{
    cin >> n >> k;

    memset(dp, -0x3f3f3f3f, sizeof(dp) );

    k++;

    for (int i = 1; i <= n; i++)
        scanf("%d", &ar[i]), pref[i] = pref[i - 1] + ar[i];

    dp[0][0] = 0;

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

    cout << dp[k & 1][n] << endl;

    while (k > 1)
    {
        printf("%d ", p[k][n]);
        n = p[k][n];
        k--;
    }
}

Compilation message (stderr)

sequence.cpp: In function 'void compute(long long int, long long int, long long int, long long int, long long int)':
sequence.cpp:42:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
         if (dp[k & 1 ^ 1][i] + (pref[md] - pref[i]) * (pref[n] - pref[md]) > dp[k & 1][md] )
                  ^
sequence.cpp:44:34: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
             dp[k & 1][md] = dp[k & 1 ^ 1][i] + (pref[md] - pref[i]) * (pref[n] - pref[md]);
                                  ^
sequence.cpp: At global scope:
sequence.cpp:54:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
sequence.cpp: In function 'int main()':
sequence.cpp:63:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d", &ar[i]), pref[i] = pref[i - 1] + ar[i];
                           ^
sequence.cpp:74:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
         printf("%d ", p[k][n]);
                              ^
sequence.cpp:63:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]), pref[i] = pref[i - 1] + ar[i];
                                                           ^

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