Submission #441776

#	Time	Username	Problem	Language	Result	Execution time	Memory
441776		Thienu	Split the sequence (APIO14_sequence)	C++17	100 / 100	925 ms	81604 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define u_map unordered_map
#define u_set unordered_set
#define u_multiset unordered_multiset

using ll = long long;
using vvi = vector<vector<int>>;
using vi = vector<int>;
using vvll = vector<vector<long long>>;
using vll = vector<long long>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

struct Line{
    ll m, c;
    int idx;
    Line(ll _m, ll _c, int _idx) : m(_m), c(_c), idx(_idx) {}

    ll eval(ll x){
        return m * x + c;
    }
};
void __print(Line x) {cerr << "{m=" << x.m << ", c=" << x.c << '}';}

// floored division, source: kactl
ll divide(ll a, ll b) {
	return a / b - ((a ^ b) < 0 && a % b);
}

// returns floor(x), x is where lines intercept
ll line_intersection(Line l1, Line l2){
    assert(l1.m != l2.m);
    return divide(l2.c-l1.c, l1.m-l2.m);
}

// queries and slopes both in nondecreasing order
struct CHT{
    deque<Line> q;

    Line eval(ll x){
        debug("eval", x);
        // debug(q.size(), q.front());
        // if(q.size() > 1){
        //     debug(*next(q.begin()));
        // }
        assert(!q.empty());
        while(q.size() > 1 && q.front().eval(x) <= next(q.begin())->eval(x)){
            q.pop_front();
        }
        return q.front();
    }

    void add(Line l){
        debug("add", l);
        if(!q.empty() && l.m == q.back().m){
            if(l.c < q.back().c){
                return;
            }else{
                q.pop_back();
            }
        }
        // if(q.size() > 1){
        //     debug(line_intersection(q.back(), *prev(prev(q.end()))), line_intersection(q.back(), l));
        // }
        while(q.size() > 1 && line_intersection(q.back(), *prev(prev(q.end()))) >= line_intersection(q.back(), l)){
            q.pop_back();
        }
        q.push_back(l);
    }
};

const int MAXN = 1e5 + 10;
const int MAXK = 202;

int last[MAXK][MAXN];
ll dp[2][MAXN];
int a[MAXN];
int pref[MAXN];

void solve(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    pref[0] = 0;
    for(int i = 1; i <= n; i++){
        pref[i] = pref[i-1] + a[i-1];
    }

    // fill dp, k=0
    for(int j = 0; j <= n; j++){
        dp[0][j] = 0;
    }
    for(int i = 1; i <= k; i++){
        debug(i);
        // fix memory limit
        int new_i = i & 1;
        int old_i = new_i ^ 1;
        
        CHT cht;
        for(int j = i+1; j <= n; j++){
            debug(j, pref[j-1]);
            cht.add(Line(pref[j-1], dp[old_i][j-1] - 1LL * pref[j-1] * pref[j-1], j-1));

            Line l = cht.eval(pref[j]);
            dp[new_i][j] = l.eval(pref[j]);
            debug(l, dp[new_i][j]);
            last[i][j] = l.idx;
        }
    }
    cout << dp[k & 1][n] << endl;

    int cur = n;
    for(int i = k; i >= 1; i--){
        cur = last[i][cur];
        cout << cur << ' ';
    }
    cout << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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