Submission #37454

#	Time	Username	Problem	Language	Result	Execution time	Memory
37454		Just_Solve_The_Problem	Split the sequence (APIO14_sequence)	C++11	0 / 100	2000 ms	20204 KiB

sequence

#include <cstdio>
#include <vector>

using namespace std;

#define pb push_back
#define ll long long

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

int a[N];
ll pref[N];
ll ans = 0;
int n, k;
vector < int > anss;

int max (int a, int b) {
    return (a < b) ? b : a;
}

void go (int pos, int kk, int last, ll sum, vector < int > vec = vector < int > ()) {
    if (k + 1 == kk) {
        if (sum > ans) {
            ans = sum;
            anss = vec;
        }
        return ;
    } else if (pos == n) {
        return ;
    }
    vec.pb(pos);
    go(pos + 1, kk + 1, pos, sum + (pref[n] - pref[pos]) * (pref[pos] - pref[last]), vec);
    vec.pop_back();
    go(pos + 1, kk, last, sum, vec);
}

main () {
    scanf ("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", a + i);
    }
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i];
    }
    go (1, 1, 0, 0);
    printf ("%lld\n", ans);
    for (int to : anss) {
        printf ("%d ", to);
    }
}

Compilation message (stderr)

sequence.cpp:37:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
sequence.cpp: In function 'int main()':
sequence.cpp:38:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &n, &k);
                            ^
sequence.cpp:40:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", a + 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