結果

問題 No.1248 Kth Sum
ユーザー t33ft33f
提出日時 2020-10-03 10:01:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 326 ms / 2,000 ms
コード長 2,552 bytes
コンパイル時間 911 ms
コンパイル使用メモリ 95,852 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2024-07-18 04:09:39
合計ジャッジ時間 6,640 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 76 ms
6,944 KB
testcase_14 AC 178 ms
12,544 KB
testcase_15 AC 74 ms
6,940 KB
testcase_16 AC 219 ms
14,464 KB
testcase_17 AC 219 ms
14,464 KB
testcase_18 AC 211 ms
14,208 KB
testcase_19 AC 211 ms
14,464 KB
testcase_20 AC 209 ms
14,336 KB
testcase_21 AC 201 ms
14,208 KB
testcase_22 AC 166 ms
12,544 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 208 ms
15,104 KB
testcase_25 AC 326 ms
15,104 KB
testcase_26 AC 225 ms
14,720 KB
testcase_27 AC 75 ms
6,940 KB
testcase_28 AC 75 ms
6,940 KB
testcase_29 AC 75 ms
6,940 KB
testcase_30 AC 171 ms
14,592 KB
testcase_31 AC 148 ms
14,336 KB
testcase_32 AC 147 ms
14,464 KB
testcase_33 AC 2 ms
6,940 KB
testcase_34 AC 270 ms
14,592 KB
testcase_35 AC 225 ms
14,336 KB
testcase_36 AC 226 ms
14,336 KB
testcase_37 AC 206 ms
13,952 KB
権限があれば一括ダウンロードができます

ソースコード

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