제출 #979847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979847		vjudge1	수열 (APIO14_sequence)	C++17	49 / 100	784 ms	131072 KiB

sequence

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int    long long
#define endl '\n' 
#define sz(x) (int)(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define uniq(v) (v).erase(unique(all(v)),(v).end())
typedef tree<int, null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> pbds;//A.find_by_order(x), A.order_of_key(x)
const long long INF=1e18;
const int mod=1e9+7;  // 998244353;

void dgb_out () { cerr << endl; }
template < typename Head, typename... Tail >
void dgb_out ( Head H, Tail... T) { cerr <<' ' << H; dgb_out (T...); }
#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dgb_out(__VA_ARGS__) 
#else
#define dbg(...)
#endif

int m, n;
vector<long long> dp_before, dp_cur;
vector<int> arr, pref, ans;
const int N = 1e5 + 5, K = 205;
int par[K][N];
// int cur_l = 1, cur_r = 0, ans = 0;
long long C(int i, int j){
    return -(pref[j] - (i == 0 ? 0 : pref[i-1])) * (pref[n-1] - pref[j]);
}

void print_ans(int i, int k){
    if(k >= 0){
        // cout<<i<<" "<<par[k][i]<<endl;
        ans.push_back(i);
        // if(i < 0)done = 0;
        // if(done == -1) 
        print_ans(par[k][i], k-1);
        // else print_ans(0, k-1, done);
    }
}

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr, int c_k) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {LLONG_MAX, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
    }

    dp_cur[mid] = best.first;
    int opt = best.second;
    par[c_k][mid] = opt - 1;

    compute(l, mid - 1, optl, opt, c_k);
    compute(mid + 1, r, opt, optr, c_k);
}

long long solve() {
    dp_before.assign(n,0);
    dp_cur.assign(n,0);

    for (int i = 0; i < n; i++)
        dp_before[i] = C(0, i), par[0][i] = 0;

    for (int i = 1; i < m; i++) {
        compute(0, n - 1, 0, n - 1, i);
        dp_before = dp_cur;
    }

    return dp_before[n - 1];
}

signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("input.in","r", stdin);
//freopen("output.out","w", stdout);
//pbds A;
int tc=1;

// cin>>tc;
while(tc--)
{
cin>>n>>m;
arr.resize(n), pref.resize(n);
// freq.resize(n+1, 0);
for(int i=0; i<n; i++){
    cin>>arr[i];
    pref[i] = (i == 0 ? 0 : pref[i-1]) + arr[i]; 
}
m++;
cout<<-solve()<<endl;
print_ans(n-1, m-1);
sort(all(ans)); ans.pop_back();
assert(sz(ans) == m-1);
for(int i=1; i<sz(ans); i++)assert(ans[i] != ans[i-1]);
for(auto& point : ans)cout<<point + 1<<" ";
}
    return 0;
}

// 7 3    
// 4 1 3 4 0 2 3

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