제출 #1148920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148920		blackslex	수열 (APIO14_sequence)	C++20	100 / 100	568 ms	84244 KiB

sequence

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

int n, k;

struct convex {
    struct line {
        ll m, c;
        int idx;
        line(ll m, ll c) : m(m), c(c) {}
        line(ll m, ll c, int idx) : m(m), c(c), idx(idx) {}
        ll get (ll x) {return m * x + c;}
    };
    deque<line> hull;
    bool ck (line l1, line l2, line l3) {
        return 1.l * (l1.c - l3.c) * (l2.m - l1.m) <= 1.l * (l1.c - l2.c) * (l3.m - l1.m);
    }
    void add (ll m, ll c, int idx) {
        line l(m, c, idx);
        while (hull.size() > 1 && ck(hull.end()[-2], hull.back(), l)) hull.pop_back();
        hull.emplace_back(l);
    }
    pii qr (ll x) {
        while (hull.size() > 1 && hull[1].get(x) >= hull[0].get(x)) hull.pop_front();
        return {hull[0].get(x), hull[0].idx};
    }
};

int main() {
    scanf("%d %d", &n, &k);
    vector<int> a(n + 5), pref(n + 5);
    vector<vector<ll>> dp(2, vector<ll>(n + 5));
    vector<vector<int>> par(k + 5, vector<int>(n + 5));
    convex hull;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pref[i] = pref[i - 1] + a[i];
    }
    for (int i = 1; i < n; i++) {
        dp[1][i] = 1LL * pref[i] * (pref[n] - pref[i]);
        par[1][i] = i;
    }
    for (int i = 2; i <= k; i++) {
        while (!hull.hull.empty()) hull.hull.pop_back();
        hull.add(pref[1], dp[!(i & 1)][1] - 1LL * pref[1] * pref[n], 1);
        for (int j = 2; j < n; j++) {
            auto [x, y] = hull.qr(pref[j]);
            dp[i & 1][j] = x + 1LL * pref[j] * (pref[n] - pref[j]);
            par[i][j] = y;
            hull.add(pref[j], dp[!(i & 1)][j] - 1LL * pref[j] * pref[n], j);
        }
    }
    pii xx = {0, 0};
    for (int i = 1; i < n; i++) xx = max(xx, {dp[k & 1][i], i});
    vector<pii> u{{k, xx.second}};
    while (u.back().first != 1) {
        auto [x, y] = u.back();
        u.emplace_back(x - 1, par[x][y]);
    }
    reverse(u.begin(), u.end());
    printf("%lld\n", xx.first);
    for (auto &[x, y]: u) printf("%d ", y);
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main()':
sequence.cpp:65:36: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} [-Wformat=]
   65 |     for (auto &[x, y]: u) printf("%d ", y);
      |                                   ~^    ~
      |                                    |    |
      |                                    int  std::tuple_element<1, std::pair<long long int, long long int> >::type {aka long long int}
      |                                   %lld
sequence.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

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