Submission #426270

#	Time	Username	Problem	Language	Result	Execution time	Memory
426270		zoooma13	Split the sequence (APIO14_sequence)	C++14	100 / 100	1070 ms	81464 KiB

sequence

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

int64_t sqr(int x){
    return 1LL*x*x;
}
int64_t dv(int64_t x ,int64_t y){
    return y == 0? LLONG_MAX : x/y - ((x^y) < 0 && x%y);
}

struct line{
    int64_t m ,c ,idx;
    int64_t eval(int64_t x) { return m*x + c; }
    int64_t ix(line&l) { return dv(l.c - c ,m - l.m); }
};
struct hull : deque <line> {
    void add(int64_t m ,int64_t c ,int idx){
        line l = {m ,c ,idx};
        while(size() >= 2 && l.ix(back()) <= back().ix(at(size()-2)))
            pop_back();
        push_back(l);
    }
    pair <int64_t ,int> eval(int64_t x){
        while(size() >= 2 && at(0).eval(x) <= at(1).eval(x))
            pop_front();
        return {at(0).eval(x) , at(0).idx};
    }
};

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();
        hull h;
        h.add(s[k] ,-sqr(s[k])-last_dp[k] ,k);
        for(int i = k+1; i <= n; i++){
            auto r = h.eval(2*s[i]);
            dp[i] = sqr(s[i]) - r.first;
            from[i] = r.second;
            h.add(s[i] ,-sqr(s[i])-last_dp[i] ,i);
        }
    }

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

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