Submission #426093

#	Time	Username	Problem	Language	Result	Execution time	Memory
426093		zoooma13	Split the sequence (APIO14_sequence)	C++14	50 / 100	2076 ms	3652 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

int64_t sqr(int x){
    return 1LL*x*x;
}

int main()
{
    int n ,m;
    scanf("%d%d",&n,&m);
    vector <int> a(n) ,s{0};
    for(int&i : a){
        scanf("%d",&i);
        s.push_back(s.back() + i);
    }

    vector <int64_t> dp(n+1) ,last_dp(n+1);
    vector <vector <int>> trace(1 ,vector <int> (n+1 ,0));
    for(int i = 0; i <= n; i++)
        dp[i] = sqr(s[i]);
    for(int k = 1; k <= m; k++){
        last_dp = dp;
        trace.push_back(vector <int> (n+1 ,0));
        auto&from = trace.back();
        for(int i = k+1; i <= n; i++){
            dp[i] = LLONG_MAX;
            for(int j = k; j < i; j++){
                if(dp[i] > sqr(s[i] - s[j]) + last_dp[j]){
                    dp[i] = sqr(s[i] - s[j]) + last_dp[j];
                    from[i] = j;
                }
            }
        }
    }

    printf("%lld\n",(sqr(s.back()) - dp.back()) / 2);
    for(int l = m ,i = n; l > 0; l--){
        i = trace[l][i];
        printf("%d ",i);
    }
    printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37:16: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int64_t' {aka 'long int'} [-Wformat=]
   37 |     printf("%lld\n",(sqr(s.back()) - dp.back()) / 2);
      |             ~~~^    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                |                                |
      |                long long int                    int64_t {aka long int}
      |             %ld
sequence.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d",&i);
      |         ~~~~~^~~~~~~~~

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