Submission #611941

#	Time	Username	Problem	Language	Result	Execution time	Memory
611941		Do_you_copy	Split the sequence (APIO14_sequence)	C++17	100 / 100	898 ms	94408 KiB

sequence

#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 10;

int n, k;
int a[maxN];
int trace[maxN][212];
ll dp[maxN][2];
ll pre[maxN];

struct TLine{
    ll fi, se, idx;
};

inline ld intersect(const TLine &i, const TLine &j){
    return ld(i.se - j.se) / ld(j.fi - i.fi);
}

inline ll cal(const TLine &i, int x){
    return i.fi * x + i.se;
}

struct CHT{
    deque <TLine> line;
    vector <TLine> save;
    void compile(int i){
        if (save.size() <= i) return;
        while (line.size() > 1 && (line.back().fi == save[i].fi
            || intersect(line.back(), line[line.size() - 2]) <= intersect(line.back(), save[i]))){
            line.pop_back();
        }
        line.pb(save[i]);
    }
    void add(const TLine &i){
        save.pb(i);
    }
    ll get(ll val, int i, int j){
        while (line.size() > 1 && cal(line[0], val) <= cal(line[1], val)) line.pop_front();
        trace[i][j] = line[0].idx;
        return cal(line[0], val);
    }
    void clear(){
        line.clear();
        save.clear();
    }
};
CHT S[2];

void Init(){
    cin >> n >> k;
    ++k;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    S[0].add({0, 0, 0});
    for (int _ = 1; _ <= k; ++_){
        int i = _ % 2;
        S[i].clear();
        for (int j = _; j <= n - (k - _); ++j){
            S[i ^ 1].compile(j - _);
            ll val = pre[n] - pre[j];
            dp[j][i] = S[i ^ 1].get(val, j, _) + pre[j] * val;
            TLine newline = {-pre[j], dp[j][i], j};
            S[i].add(newline);
        }
    }
    cout << dp[n][k % 2] << "\n";
    while (trace[n][k]){
        cout << trace[n][k] << " ";
        n = trace[n][k];
        --k;
    }
}

signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message (stderr)

sequence.cpp: In member function 'void CHT::compile(int)':
sequence.cpp:52:25: warning: comparison of integer expressions of different signedness: 'std::vector<TLine>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         if (save.size() <= i) return;
      |             ~~~~~~~~~~~~^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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