제출 #989446

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

sequence

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pll = pair<long long, long long>;
 
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 1e5 + 2;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 520;
const ll base = 35711;
ll n,k;
ll a[N], mp[N], dp[N], lst[N], ps[N];
pair<int,int> trace[N][201];
void compute(ll l, ll r, ll optl, ll optr, ll turn){
    if(l > r) return;
    ll mid = (l + r) / 2;
    pll res = {-inf, -1};
    for(int i = optl; i <= min(mid, optr);i++){
        res = max(res, {lst[i - 1] + (ps[mid] - ps[i - 1]) * (ps[i-1]), i});
    }
    trace[mid][turn] = {res.S - 1, turn - 1};
    dp[mid] = res.F;
    ll opt = res.S;
    compute(l, mid - 1, optl, opt, turn); 
    compute(mid + 1, r, opt, optr, turn);
}
/*
7 3
4 1 3 4 0 2 3
*/
void to_nho_cau(){
    cin >> n >> k;
    for(int i = 1; i <= n;i++){
        cin >> a[i];
        ps[i] = ps[i-1] + a[i];
    }
    for(int j = 1; j <= k;j++){
        compute(1, n, 1, n, j);
        for(int i = 0; i <= n;i++) lst[i] = dp[i], dp[i] = 0;
    }
    cout << lst[n] << '\n';
    ll i = n, j = k;
    while(j >= 1){
        ll nxt_i = trace[i][j].F, nxt_j = trace[i][j].S;
        i = nxt_i, j = nxt_j;
        if(i >= 1) cout << i << ' ';
    }
    cout << '\n';
}
 
signed main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;   
    //cin >> t;
    while(t--) to_nho_cau();
}

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