제출 #1248843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248843		JelalTkm	수열 (APIO14_sequence)	C++17	100 / 100	944 ms	86712 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define ll long long int
#define ld long double

const int N = 1e5 + 10;
const int md = 1e9 + 7;
// const int INF = 1e18;

struct node {
    ll k, b;
    int ind;
};

struct CHT {
  deque<node> hull;
  ll f(pair<ll, ll> line, ll x) {
    return line.first * x + line.second;
  }
  int lefff = 0;
  pair<ll, int> get(int x, int ind) {
    while ((lefff + 1) < (int) hull.size() && f({hull[lefff].k, hull[lefff].b}, x) <= f({hull[lefff + 1].k, hull[lefff + 1].b}, x) && hull[lefff + 1].ind < ind) {
        lefff++;
    }
 
    return {f({hull[lefff].k, hull[lefff].b}, x), hull[lefff].ind};
  }
  ld intersect(ll k1, ll b1, ll k2, ll b2) {
    return (ld)(b2 - b1) / (ld)(k1 - k2);
  }
  ld intersect(pair<ll, ll> line1, pair<ll, ll> line2) {
    return intersect(line1.first, line1.second, line2.first, line2.second);
  }
  void add(ll k, ll b, int ind) {
    pair<ll, ll> line = pair<ll, ll> (k, b);
    while (hull.size() > 1) {
      int s = (int) hull.size();
      if (intersect({hull[s - 2].k, hull[s - 2].b}, line) <= intersect({hull[s - 2].k, hull[s - 2].b}, {hull[s - 1].k, hull[s - 1].b})) {
        hull.pop_back();
      }
      else break;
    }
 
    hull.push_back({k, b, ind});
  }
};

int dp[N][205];

int32_t main(int32_t argc, char *argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k; k++;
        vector<int> a(n + 1);
        vector<ll> pref(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            pref[i] = pref[i - 1] + a[i];
        }

        CHT hull, hull1, hull2;
        // vector<vector<pair<int, int>>> dp(n + 1, vector<pair<int, int>> (k + 1));
        ll res = 0;
        for (int j = 1; j <= k; j++) {
            if (j != 1) {
                for (int i = j; i <= n; i++) {
                    auto xy = hull.get(pref[i], i);
                    dp[i][j] = xy.second;
                    // cout << i << " " << j << "    " << xy.first << '\n';
                    hull1.add(pref[i], -pref[i] * pref[i] + xy.first, i);
                    if (i == n && j == k)
                        res = xy.first;
                }
                
                hull = hull1;
                hull1 = hull2;
                // cout << '\n';
            } else
                for (int i = 1; i <= n; i++) {
                    hull.add(pref[i], -pref[i] * pref[i], i);
                }
        }

        cout << res << '\n';

        int i = n, j = k;
        vector<int> ans;
        while (j != 1) {
            i = dp[i][j]; j--;
            ans.push_back(i);
        }

        reverse(ans.begin(), ans.end());
        for (auto i: ans)
            cout << i << " ";
        cout << '\n';
    }

    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