제출 #37543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37543		Talant	Split the sequence (APIO14_sequence)	C++11	71 / 100	2000 ms	82880 KiB

sequence

#include <bits/stdc++.h>

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

using namespace std;


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


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

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

        int m = (l + r) >> 1;
        dp[m][k & 1] = 0;
        pr[m][k] = L;

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

        compute (k,l,m - 1,L,pr[m][k]);
        compute (k,m + 1,r,pr[m][k],R);
}

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

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

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

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

        id = n;

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

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'void compute(int, int, int, int, int)':
sequence.cpp:34:34: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                 ll now = dp[i][k & 1 ^ 1] + calc(m,i);
                                  ^
sequence.cpp: In function 'int main()':
sequence.cpp:49:35: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
                 scanf ("%d", &p[i]);
                                   ^
sequence.cpp:46: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:49:36: 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: 0 / 29