Submission #37510

#	Time	Username	Problem	Language	Result	Execution time	Memory
37510		Talant	Split the sequence (APIO14_sequence)	C++11	Compilation error	0 ms	0 KiB

sequence

#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e9 + 7;
const int N = (int)1e5 + 2;

int n,k,id;
int a[N];
int cnt,o;

int p[N];
ll mx;
ll dp[n + 1][k + 1];

ll calc (int r,int l) {
        return (p[r] - p[l]) * 1ll * (p[n] - p[r]);
}
void compute (int k,int l,int r,int L,int R) {
        if (l > r)
                return;

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

        for (int i = L; i <= min(m,R); i ++) {
                ll now = dp[i - 1][(k - 1)] + calc(m,i - 1);
                if (now > dp[m][k])
                        dp[m][k ] = now,opt = i;
        }
        pr[m][k] = opt;

        compute (k,l,m - 1,L,opt);
        compute (k,m + 1,r,opt,R);
}
int main () {
        scanf ("%d%d", &n,&k);

        o = k;

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

        for (int i = 1; i <= n; i ++) {
                dp[i][1] = calc(i,0);
                pr[i][1] = 1;
        }

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

        for (int i = 1; i <= n; i ++) {
                if (mx < dp[i][k ])
                        mx = max(mx,dp[i][k ]),id = i;
        }

        printf("%lld\n", mx);

        deque<int> dq;

        while (id > 0 && k > 0) {
                if (cnt == o)
                        break;
                dq.push_front(id);
                id = pr[id][k] - 1;
                k --;
                cnt ++;
        }
        for (int i = 0; i < (int)dq.size(); i ++)
                printf("%d ", dq[i]);
}
/**
7 3
4 1 3 4 0 2 3
**/

Compilation message (stderr)

sequence.cpp:22:12: error: array bound is not an integer constant before ']' token
 ll dp[n + 1][k + 1];
            ^
sequence.cpp:22:19: error: array bound is not an integer constant before ']' token
 ll dp[n + 1][k + 1];
                   ^
sequence.cpp: In function 'void compute(int, int, int, int, int)':
sequence.cpp:35:26: error: 'dp' was not declared in this scope
                 ll now = dp[i - 1][(k - 1)] + calc(m,i - 1);
                          ^
sequence.cpp:39:9: error: 'pr' was not declared in this scope
         pr[m][k] = opt;
         ^
sequence.cpp: In function 'int main()':
sequence.cpp:50:37: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
                 scanf ("%lld", &a[i]);
                                     ^
sequence.cpp:55:17: error: 'dp' was not declared in this scope
                 dp[i][1] = calc(i,0);
                 ^
sequence.cpp:56:17: error: 'pr' was not declared in this scope
                 pr[i][1] = 1;
                 ^
sequence.cpp:63:26: error: 'dp' was not declared in this scope
                 if (mx < dp[i][k ])
                          ^
sequence.cpp:75:22: error: 'pr' was not declared in this scope
                 id = pr[id][k] - 1;
                      ^
sequence.cpp:45:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d%d", &n,&k);
                              ^
sequence.cpp:50:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%lld", &a[i]);
                                      ^