結果

問題 No.1248 Kth Sum
ユーザー msm1993
提出日時 2020-10-23 15:29:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 284 ms / 2,000 ms
コード長 2,552 bytes
コンパイル時間 1,054 ms
コンパイル使用メモリ 88,616 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2024-07-21 10:06:38
合計ジャッジ時間 6,244 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:17:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   17 |         for (auto [x, y] : S) cerr << "(" << x << ", " << y << "); ";
      |                   ^
main.cpp:20:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   20 |         for (auto [x, y] : T) cerr << "(" << x << ", " << y << "); ";
      |                   ^
main.cpp: In function 'long long int solve(int, int, int*)':
main.cpp:41:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   41 |     for (auto &[val, idx] : T) sum += val;
      |                ^

ソースコード

diff # 

#include <vector>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <set>
#include <iostream>
using namespace std;

long long solve(int n, int k, int *a) {
    if (k == 1) return a[0];
    if (2 * k > n) return a[k-1];

    set<pair<int, int> > S, T;
    set<int> U;
    auto dump = [&]() -> void {
        cerr << "S = ";
        for (auto [x, y] : S) cerr << "(" << x << ", " << y << "); ";
        cerr << endl;
        cerr << "T = ";
        for (auto [x, y] : T) cerr << "(" << x << ", " << y << "); ";
        cerr << endl;
        cerr << "U = ";
        for (int u : U) cerr << u << ' ';
        cerr << endl;
    };

    int segmin[n];
    for (int m = 1; m * (k - 1) < n; m++)
        segmin[m] = *min_element(a + (m-1) * (k-1) + 1, a + m * (k - 1) + 1);
    int sufmin[n];
    sufmin[n-1] = a[n-1];
    for (int i = n-2; i >= 0; i--) sufmin[i] = min(sufmin[i+1], a[i]);

    for (int i = k; i < n; i++) S.insert({a[i], i});
    for (int i = 0; i < 2; i++) {
        U.insert(S.begin()->second);
        T.insert(*S.begin());
        S.erase(S.begin());
    }
    long long sum = 0;
    for (auto &[val, idx] : T) sum += val;
    long long ans = a[k-1];
    for (int i = 0, m = 2; m * k <= n; m++) {
        int c = 0;
        long long tmp = sum;
        if (*U.begin() > m * (k - 1)) {
            c++;
            tmp += segmin[m];
            // cerr << "left " << tmp << endl;
        }
        if (*U.rbegin() < m*k-1) {
            c++;
            tmp += sufmin[m*k-1];
            // cerr << "right " << tmp << endl;
        }
        if (c > 0) tmp -= T.rbegin()->first;
        if (c > 1) tmp -= next(T.rbegin())->first;
        ans = min(ans, tmp);
        // dump();
        // cerr << "m = " << m << " => " << tmp << "; sum = " << sum << "; c = " << c << endl;

        if ((m + 1) * k > n) break;

        c = 1;
        for (int i = (m-1)*(k-1)+1; i <= m*(k-1); i++) {
            if (U.find(i) != U.end()) {
                c++;
                sum -= a[i];
                T.erase({a[i], i});
                U.erase(i);
            } else
                S.erase({a[i], i});
        }
        while (c--) {
            auto it = S.begin();
            sum += it->first;
            T.insert(*it);
            U.insert(it->second);
            // cerr << "add " << it->first << " " << it->second << endl;
            S.erase(it);
        }
    }
    return ans;
}

int main() {
    int n, k; cin >> n >> k;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
    
    cout << solve(n, k, a) << endl;
}
0