Submission #226354

#	Time	Username	Problem	Language	Result	Execution time	Memory
226354		dandrozavr	Split the sequence (APIO14_sequence)	C++14	54 / 100	100 ms	131076 KiB

sequence

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /◐/  /▐/   /▌/ /▀/ /░/ /  / choose your own style!

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/


//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#include <bits/stdc++.h>
using namespace std ;
#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container) {for (auto &u : container)os << u << " ";return os;} template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) {return os << p.first << " " << p.second;}template <class T> ostream &operator<<(ostream &os, set<T> const& con) {    for (auto &u : con)        os << u << " ";return os;} void pr() {} template <typename T, typename... args> void pr(T x, args... tail) {cout << x << " ";pr(tail...);}} using namespace fastio;

#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
mt19937_64 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 2e5 + 3;
const int M = 1e9 + 7;

struct CHT{
    deque < pair < ll , pair < ll, int > > > q;
    int del = 0;
    ll div(ll a, ll b){
        // b2 - b1, k1 - k2
        return a / b - ((a ^ b) && (a % b));
    }

    void add(ll k, ll b, int i){
        pair < ll , pair < ll, int > >  z = {k, {b, i}};
        while(q.size() > 1){
            auto y = q.back();
            auto x = q[q.size() - 2];
            if (y.F == z.F){
                if (y.S.F > z.S.F) return;
                q.pop_back();
                continue;
            }
            if (div(z.S.F - y.S.F, y.F - z.F) <= div(y.S.F - x.S.F, x.F - y.F)) q.pop_back();
                else break;
        }
        if (q.size() && q.back().F == z.F){
            if (q.back().S.F > z.S.F) return; q.pop_back();
        }
        q.pb(z);
    }

    pair < ll , int > get(ll X){
        while(q.size() > 1){
            auto x = q[0];
            auto y = q[1];
            if (x.F * X + x.S.F <= y.F * X + y.S.F) q.pop_front(); else break;
            ++del;
        }
        return make_pair(q[0].F * X + q[0].S.F, q[0].S.S);
    }
};


main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #ifdef Estb_probitie
        freopen("input.txt", "r", stdin);
        freopen("output1.txt", "w", stdout);
    #endif

    int n, k;
    cin >> n >> k;
    ll a[n], pref[n];
    for (int i = 0; i < n; ++i){
        cin >> a[i];
        pref[i] = a[i];
        if (i) pref[i] += pref[i - 1];
    }
    ll dp[n][k + 1] = {};
    int Pr[n][k + 1];

    CHT all[k + 2];


    for (int K = 1; K <= k; ++K){
        all[K].add(pref[0], 0 - a[0] * a[0], 0);
        for (int i = 1; i < n; ++i){
            auto func = all[K].get(pref[i]);
            dp[i][K] = func.F;
            Pr[i][K] = func.S;
            all[K].add(pref[i], dp[i][K - 1] - pref[i] * pref[i], i);
        }
    }

    int v = n - 1;
    cout << dp[v][k]<<endl;
    for (int i = k; i > 0; --i){
        v = Pr[v][i];
        cout << v + 1 << " ";
    }


}

Compilation message (stderr)

sequence.cpp: In member function 'void CHT::add(long long int, long long int, int)':
sequence.cpp:76:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if (q.back().S.F > z.S.F) return; q.pop_back();
             ^~
sequence.cpp:76:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
             if (q.back().S.F > z.S.F) return; q.pop_back();
                                               ^
sequence.cpp: At global scope:
sequence.cpp:93:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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